[Math] Determining whether a number is a ‘factorial number’

algorithmsfactorial

Let's define $\mathbb{F}=\{x \in \mathbb{Z^+}: x=n!, n=\mathbb{N}\}$ to be the set of all 'factorial numbers' (i.e. all positive integers which are the factorial of some natural number).

Is there an efficient way to determine, given any positive integer $x,$ whether $x \in \mathbb{F} \quad$?

I'm looking for a method analogous to the primality test for primes– which says that, if, for all $n \leqslant \left\lfloor \sqrt{p} \right\rfloor$ (where $n \in \mathbb{Z^+}$), $n \nmid p$, then $p$ is prime– though I'm open to any method that gets the job done.


$\underline{\text{My thoughts :}}$

I know that it's not as simple as seeing whether $2 \mid x,\ 3|x, \ 4|x$, etc., as, for example, $2|12, \ 3|12, \ 4|12$ but $5 \nmid 12 \quad ,$ (so one may erroneously conclude that $12=4! \in \mathbb{F}$).

A very inelegant (and inefficient) way to do this is obviously to compute $\color{green}{1! \ , 2! \ , 3! \ , \cdots \, \ m!} \ $, for sufficiently large $m$, and then to check whether $x$ is equal to one of $\color{green}{\text{these}}$ numbers (and if not, then $x \notin \mathbb{F}$).

Can anyone suggest a less-time-consuming method for determining whether is a number is a 'factorial number'?

Best Answer

Divide $x$ by $2$, then divide by $3$, and so on, until you cannot divide further. If you arrive at the number $1$, you started with a factorial. Otherwise you didn't.

Related Question