<p>If you want to use primes a <a href="https://www.cecm.sfu.ca/%7Epborwein/PAPERS/P29.pdf" rel="nofollow noreferrer" title="Peter B. Borwein: On the complexity of calculating factorials">result by Peter Borwein</a> is <span class="math-container">$O(log log n M( n log n))$</span> where <span class="math-container">$n$</span> is the bits of <span class="math-container">$P$</span> and <span class="math-container">$M$</span> is the run time of your fast multiplication algorithm.</p>
<p>I have created a <a href="https://gist.github.com/chadbrewbaker/8445183" rel="nofollow noreferrer">worksheet</a> in Ruby to demonstrate a few. Even for <span class="math-container">$N=10000$</span> you get at least twice the speed of the brute force approach.</p>
<pre><code>              user     system      total        real
</code></pre>
<p>Primal: 4.742000 0.296000 5.038000 ( 5.045505)</p>
<p>Primal memo: 0.921000 0.000000 0.921000 ( 0.910091)</p>
<p>Brute: 10.186000 1.560000 11.746000 ( 11.760176)</p>
<p>interval 5: 0.500000 0.000000 0.500000 ( 0.496049)</p>
<p>interval 10: 0.514000 0.000000 0.514000 ( 0.511051)</p>
<p>interval 100: 0.515000 0.031000 0.546000 ( 0.539054)</p>
<p>interval 512: 0.515000 0.047000 0.562000 ( 0.574058)</p>
<p>Unique values (should be 1): 1</p>
<p>Some things to note. Cache efficiency matters once numbers get large enough. Also <span class="math-container">$M(n)$</span> is a bad bound of the fast multiplication run time. You want to use <span class="math-container">$M(a,b)$</span> because multiplying a huge number repeatedly by small numbers is a waste when you can reduce the small ones first.</p>
<p>As requested by @Artem if <span class="math-container">$N$</span> is not specified then you have to do a bit more book-keeping.</p>
<p>It helps if you look at N! in binary: 1, 10, 110, 11000, 1111000, 1011010000, 1001110110000</p>
<p>Notice the number of trailing zeros identifies <span class="math-container">$N$</span> within one. See <a href="https://oeis.org/A011371" rel="nofollow noreferrer">https://oeis.org/A011371</a></p>
<p>Compute the factorial of <span class="math-container">$N=2k$</span> using Borwein's method and match it against <span class="math-container">$P$</span>, if necessary multiply one more number to get <span class="math-container">$N=2k+1$</span>.</p>

CC BY-SA 3.0
2014-02-13T19:18:18.267Z
Chad, you can add the information about how to decide if $P$ is the factorial of some number $N$ (where only $P$ is given). I do not understand from your comment how you reduce this to computing a single factorial? (the lookup table in my answer is of size 4 by the way, it doesn't make much of a difference)
Sasho Nikolov
CC BY-SA 3.0
2014-02-13T21:20:36.850Z
This statement is false: "Notice that the number of trailing zeros identifies $N$ within one, $N = 2k$ or $N = 2k + 1$", if we assume by $k$ you mean that $N!$ is divisible by $2^k$ but not by $2^{k + 1}$.
Artem Kaznatcheev
CC BY-SA 3.0
2014-02-13T21:29:03.213Z
$3! = 2^1*3$ but $4! = 2^3*3$; $7! = 2^4*315$ but $8! = 2^7*315$; $15! = 2^{11}*638512875$ but $16! = 2^{15}*638512875$, hopefully you can guess how I'm picking the numbers ;).
Artem Kaznatcheev
CC BY-SA 3.0
2014-02-13T22:44:15.047Z
@Artem I think he is saying that if $m_2(N!)$ is the largest power of 2 dividing N!, then $m_2((N+2)!) > m_2(N!)$. then you can compute the smallest $N$ such that $m_2(N!) = m_2(P)$ (if one exists) given $P$ in time  $m_2(P)\log^{O(1)}m_2(P)$ by just iterating over $N$ and adding up powers of 2.
Sasho Nikolov
CC BY-SA 3.0
2014-02-14T03:40:49.180Z
Chad, for a more complete answer, I think you need to argue that you can invert the sequence A011371 fast enough, not just that the multiplicity of any element in it is at most 2.
Sasho Nikolov
CC BY-SA 3.0
2014-02-14T17:48:25.310Z
No need for a closed form. You can brute the inverse in log2(#zeros) calls to OEIS_A01137(i); which is asymptotically negligible compared to cranking out the rest of the primes for Borwien's method.
Chad Brewbaker
CC BY-SA 3.0
2014-02-01T18:12:04.723Z
If you re-format your table's look and feel that would be nice.
reza
CC BY-SA 3.0
2014-02-11T22:00:45.477Z
@RezaHasanzadeh this does not answer your question. Chad's answer cites a paper that shows how to given $N$ computes $N!$, not how given $P$ decide if there is some $N$ such that $P = N!$. You need the trick in Sasho's comment to actually answer your question. I think this 'answer' should be a comment.
Artem Kaznatcheev
CC BY-SA 4.0
2014-01-15T20:31:21.223Z
2022-12-30T20:14:21.880Z
2022-12-30T20:14:21.880Z
Chad Brewbaker
<p>Notice that the input size is <span class="math-container">$n = \lceil \log_2 P \rceil$</span>. The problem can be solved in time near linear in <span class="math-container">$n$</span>, i.e. in time <span class="math-container">$n \log^{O(1)} n = (\log P)(\log \log P)^{O(1)}$</span>.</p>
<p>The trick is to do binary search on the integers in <span class="math-container">$[1, 2\log_2 P]$</span> in order to find the largest <span class="math-container">$N$</span> such that <span class="math-container">$N! \leq P$</span>: call this number <span class="math-container">$N(P) = \max\{N: N! \leq P\}$</span>. If <span class="math-container">$N(P) = P$</span>, the answer is 'yes', otherwise it is 'no'.</p>
<p>Let us first show that <span class="math-container">$N(P) \leq 2\log_2 P$</span> for <span class="math-container">$P \geq 4$</span> (for smaller <span class="math-container">$P$</span> you can use a lookup table). This follows because for every <span class="math-container">$N$</span>, <span class="math-container">$N! \geq (N/2)^{N/2}$</span>, and therefore
<span class="math-container">$$
\log_2 P \geq \frac{N}{2}\log_2 \frac{N}{2} \geq \frac{N}{2}.
$$</span></p>
<p>The complexity is <span class="math-container">$T(2\log_2 P) \cdot O(\log \log P)$</span>, whete <span class="math-container">$T(N!)$</span> is the complexity of computing <span class="math-container">$N!$</span>. This is because the binary search performs <span class="math-container">$O(\log \log P)$</span> steps, and at each step computes <span class="math-container">$N!$</span> for some <span class="math-container">$N \leq 2\log_2 P$</span>. The <a href="https://www.cecm.sfu.ca/%7Epborwein/PAPERS/P29.pdf" rel="nofollow noreferrer" title="Peter B. Borwein: On the complexity of calculating factorials">work by Borwein</a>, referenced in Chad's answer, gives a near-linear in <span class="math-container">$N$</span> bound on <span class="math-container">$T(N)$</span>.</p>

CC BY-SA 4.0
2014-02-12T01:07:41.903Z
2022-12-30T20:14:27.210Z
2022-12-30T20:14:27.210Z
Sasho Nikolov
<p>How efficiently can we decide that a number $P$ is the result of the factorial of another number $N$ (i.e. $P = N!$)? Notice that $P$ and $N$ are both integers and we are only given $P$.</p>

CC BY-SA 3.0
2014-01-15T21:25:17.070Z
I suppose you are only given $P$. An algorithm can be: set $n=2$ and $p=P$; while the division $p/n$ is exact and $p\neq1$, $p\gets p/n$ & $n\gets n+1$. At the end, you answer depending on whether you attained $1$ or you had a non exact division. Let $N$ be minimal such that $P\ge N!$. Since $2^N<N!$, $N<\log P$ and you perform at most $\log P$ divisions. I think you can thus bound the complexity of this algorithm by $O(\log^2 P)$.
Bruno
CC BY-SA 3.0
2014-01-15T23:50:59.283Z
You can do binary search on the integers in the interval $[1, 2\log_2 P]$ to find the largest integer $N$ such that $N! \leq P$. Then check if $N! = P$. Since, $\log_2 P \geq \log_2 N! \geq (N/2)\log_2 (N/2)$, you have that $N \leq 2 \log_2 P$ for $N \geq 4$ (for $P \leq 4!$ you can use a look up table). This has complexity $T(2\log_2 P)*O(\log\log P)$, where $T(N)$ is the complexity of computing $N!$, which is near-linear in $N$. So the complexity is near-linear in the input size, i.e. $\log_2 P$.
Sasho Nikolov
CC BY-SA 3.0
2014-02-01T18:04:01.880Z
@Bruno Yes, we are only given *P*.
reza
CC BY-SA 3.0
2014-02-11T21:59:07.607Z
@SashoNikolov you should give this as an answer. The current answer cites a paper that shows how to given $N$ computes $N!$, not how given $P$ decide if there is some $N$ such that $P = N!$. Of course, you can use the paper in Chad's answer to give a more precise upper bound on $T$.
Artem Kaznatcheev
<ds.algorithms>
Factoriality testing algorithms and their efficiency
reza
# Factoriality testing algorithms and their efficiency

(Asked by: username_0 on 2014-01-15)

How efficiently can we decide that a number $P$ is the result of the factorial of another number $N$ (i.e. $P = N!$)? Notice that $P$ and $N$ are both integers and we are only given $P$.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: I suppose you are only given $P$. An algorithm can be: set $n=2$ and $p=P$; while the division $p/n$ is exact and $p\neq1$, $p\gets p/n$ & $n\gets n+1$. At the end, you answer depending on whether you attained $1$ or you had a non exact division. Let $N$ be minimal such that $P\ge N!$. Since $2^N<N!$, $N<\log P$ and you perform at most $\log P$ divisions. I think you can thus bound the complexity of this algorithm by $O(\log^2 P)$.  
> **username_2**: You can do binary search on the integers in the interval $[1, 2\log_2 P]$ to find the largest integer $N$ such that $N! \leq P$. Then check if $N! = P$. Since, $\log_2 P \geq \log_2 N! \geq (N/2)\log_2 (N/2)$, you have that $N \leq 2 \log_2 P$ for $N \geq 4$ (for $P \leq 4!$ you can use a look up table). This has complexity $T(2\log_2 P)*O(\log\log P)$, where $T(N)$ is the complexity of computing $N!$, which is near-linear in $N$. So the complexity is near-linear in the input size, i.e. $\log_2 P$.  
> **username_0**: @username_1 Yes, we are only given *P*.  
> **username_3**: @SashoNikolov you should give this as an answer. The current answer cites a paper that shows how to given $N$ computes $N!$, not how given $P$ decide if there is some $N$ such that $P = N!$. Of course, you can use the paper in Chad's answer to give a more precise upper bound on $T$.  

---

## 2 answers

### Answer by username_2 on 2014-02-12. Score: 9 | Accepted answer

Notice that the input size is $n = \lceil \log\_2 P \rceil$. The problem can be solved in time near linear in $n$, i.e. in time $n \log^{O(1)} n = (\log P)(\log \log P)^{O(1)}$.

The trick is to do binary search on the integers in $[1, 2\log\_2 P]$ in order to find the largest $N$ such that $N! \leq P$: call this number $N(P) = \max\{N: N! \leq P\}$. If $N(P) = P$, the answer is 'yes', otherwise it is 'no'.

Let us first show that $N(P) \leq 2\log\_2 P$ for $P \geq 4$ (for smaller $P$ you can use a lookup table). This follows because for every $N$, $N! \geq (N/2)^{N/2}$, and therefore
$$
\log\_2 P \geq \frac{N}{2}\log\_2 \frac{N}{2} \geq \frac{N}{2}.
$$

The complexity is $T(2\log\_2 P) \cdot O(\log \log P)$, whete $T(N!)$ is the complexity of computing $N!$. This is because the binary search performs $O(\log \log P)$ steps, and at each step computes $N!$ for some $N \leq 2\log\_2 P$. The [work by Borwein](https://www.cecm.sfu.ca/%7Epborwein/PAPERS/P29.pdf "Peter B. Borwein: On the complexity of calculating factorials"), referenced in Chad's answer, gives a near-linear in $N$ bound on $T(N)$.


---

### Answer by username_4 on 2014-01-15. Score: 4

If you want to use primes a result by Peter Borwein is $O(log log n M( n log n))$ where $n$ is the bits of $P$ and $M$ is the run time of your fast multiplication algorithm.
I have created a worksheet in Ruby to demonstrate a few. Even for $N=10000$ you get at least twice the speed of the brute force approach.
              user     system      total        real

Primal: 4.742000 0.296000 5.038000 ( 5.045505)
Primal memo: 0.921000 0.000000 0.921000 ( 0.910091)
Brute: 10.186000 1.560000 11.746000 ( 11.760176)
interval 5: 0.500000 0.000000 0.500000 ( 0.496049)
interval 10: 0.514000 0.000000 0.514000 ( 0.511051)
interval 100: 0.515000 0.031000 0.546000 ( 0.539054)
interval 512: 0.515000 0.047000 0.562000 ( 0.574058)
Unique values (should be 1): 1
Some things to note. Cache efficiency matters once numbers get large enough. Also $M(n)$ is a bad bound of the fast multiplication run time. You want to use $M(a,b)$ because multiplying a huge number repeatedly by small numbers is a waste when you can reduce the small ones first.
As requested by @Artem if $N$ is not specified then you have to do a bit more book-keeping.
It helps if you look at N! in binary: 1, 10, 110, 11000, 1111000, 1011010000, 1001110110000
Notice the number of trailing zeros identifies $N$ within one. See https://oeis.org/A011371
Compute the factorial of $N=2k$ using Borwein's method and match it against $P$, if necessary multiply one more number to get $N=2k+1$.

> **Comments:**
> **username_0**: If you re-format your table's look and feel that would be nice.  
> **username_3**: @RezaHasanzadeh this does not answer your question. Chad's answer cites a paper that shows how to given $N$ computes $N!$, not how given $P$ decide if there is some $N$ such that $P = N!$. You need the trick in Sasho's comment to actually answer your question. I think this 'answer' should be a comment.  
> **username_2**: Chad, you can add the information about how to decide if $P$ is the factorial of some number $N$ (where only $P$ is given). I do not understand from your comment how you reduce this to computing a single factorial? (the lookup table in my answer is of size 4 by the way, it doesn't make much of a difference)  
> **username_3**: This statement is false: "Notice that the number of trailing zeros identifies $N$ within one, $N = 2k$ or $N = 2k + 1$", if we assume by $k$ you mean that $N!$ is divisible by $2^k$ but not by $2^{k + 1}$.  
> **username_3**: $3! = 2^1*3$ but $4! = 2^3*3$; $7! = 2^4*315$ but $8! = 2^7*315$; $15! = 2^{11}*638512875$ but $16! = 2^{15}*638512875$, hopefully you can guess how I'm picking the numbers ;).  
> **username_2**: @Artem I think he is saying that if $m_2(N!)$ is the largest power of 2 dividing N!, then $m_2((N+2)!) > m_2(N!)$. then you can compute the smallest $N$ such that $m_2(N!) = m_2(P)$ (if one exists) given $P$ in time  $m_2(P)\log^{O(1)}m_2(P)$ by just iterating over $N$ and adding up powers of 2.  
> **username_2**: Chad, for a more complete answer, I think you need to argue that you can invert the sequence A011371 fast enough, not just that the multiplicity of any element in it is at most 2.  
> **username_4**: No need for a closed form. You can brute the inverse in log2(#zeros) calls to OEIS_A01137(i); which is asymptotically negligible compared to cranking out the rest of the primes for Borwien's method.  

---

