4
$\begingroup$

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

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

2 Answers 2

9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .