Prime factorization of factorials

Question

Is there a way given a sequence of naturals $a_1, a_2, ..., a_k$ to determine whether $c=n!$ for some number $n$ where $$ c = 2^{a_1} 3^{a_2}5^{a_3}7^{a_4}...$$ (2,3,5,7,... - primes)

Answer 1

$$n! = \prod_p p^{\sum_{k \ge 1} k \lfloor n/p^k\rfloor}$$

• You are given a prime decomposition $A =\prod_p p^{a_p}$ and you want to know if it exists $r$ such that $r! = \prod_p p^{a_p}$. Of course you can compute $A$ and use the dichotomy for finding $r$.

• Otherwise, note that if $n$ is even then it is fully determinated by $a_2 = \sum_{k \ge 1} k \lfloor n/2^k\rfloor$.

  So you can make use only of $a_2$ for finding (if it exists, using dichotomy) $n$ even such that $a_2 = \sum_{k \ge 1} k \lfloor n/2^k\rfloor$.

• Then look at the other exponents for choosing if the correct result is $r = n$ or $r=n+1$, or if $A$ is not a factorial

Answer 2

Sure. Let $a_k ≥ 1$ be the last element of the series, let q be the k-th prime and r the (k+1)st prime, then q ≤ n < r. (If n < q then there's no factor q so $a_k = 0$, if n ≥ r then there's a factor r so $a_{k+1} ≥ 1$).

You can check quite easily how often a prime p is prime factor of n!. For example, 133! is the product of 133 numbers. 26 are divisible by 5, 5 are divisible by $5^2$, one is divisible by $5^3$, so 133! has a factor $5^{32}$. So for each prime p ≤ 1 you check which power of p is a factor of q! and (r-1)!. If the corresponding $a_i$ is too small for q! or too large for (r-1)! then you haven't got a factorial. Otherwise you may be able to limit the range of n.