Factoriality testing algorithms and their efficiency

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$.

• 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)$. Jan 15, 2014 at 21:25
• 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$. Jan 15, 2014 at 23:50
• @Bruno Yes, we are only given P.
– reza
Feb 1, 2014 at 18:04
• @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$. Feb 11, 2014 at 21:59

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, referenced in Chad's answer, gives a near-linear in $$N$$ bound on $$T(N)$$.

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$$.

• If you re-format your table's look and feel that would be nice.
– reza
Feb 1, 2014 at 18:12
• @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. Feb 11, 2014 at 22:00
• 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) Feb 13, 2014 at 19:18
• @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. Feb 13, 2014 at 22:44
• 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. Feb 14, 2014 at 3:40