4
$\begingroup$

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'?

$\endgroup$
  • 2
    $\begingroup$ "Can anyone suggest a less-time-consuming method for determining whether is a number is a 'factorial number'?" Yes. Let $n$ be large. Then $n$ is not a factorial number, with probability so close to one that there's no difference. $\endgroup$ – Stephen Sep 8 '14 at 15:06
  • $\begingroup$ Do you want it to be efficient w.r.t. the size of $x$, or w.r.t the "inverse factorial of $x$"? $\endgroup$ – JHance Sep 8 '14 at 15:16
  • $\begingroup$ Related links within: math.stackexchange.com/questions/171882/… $\endgroup$ – ClassicStyle Sep 8 '14 at 15:29
  • $\begingroup$ How large can $x$ be ? What you call the "inelegant (and inefficient) way" is probably the most efficient as regards running time, provided 1) you precompute and store all factorials, 2) you lookup the value based on the number of digits. Certainly a viable approach up to 1000 digits. $\endgroup$ – Yves Daoust Sep 10 '14 at 9:00
4
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ This should read "then divide that result by $3$..." $\endgroup$ – Emily Sep 8 '14 at 14:56
  • $\begingroup$ This method could be speeded up a little by replacing the first $n_{min}-1$ steps by a division by $n_{min}!$, where $n_{min}$ is a high lower limit for $n$ obtained using Stirling's formula. $\endgroup$ – MartinG Sep 8 '14 at 17:47
  • $\begingroup$ @MartinG: sounds like a good idea but probably not, because you will have to fully compute $n_{min}!$, which involves $n_{min}$ multiplies. By the division method, you can terminate earlier. $\endgroup$ – Yves Daoust Sep 10 '14 at 8:32
  • $\begingroup$ Yes, the time clearly depends on the outcome, but if you're fairly sure it's a factorial there would be a small gain because $n_{min}$ multiplies are quicker than $n_{min}$ divisions and associated tests. $\endgroup$ – MartinG Sep 10 '14 at 11:25
4
$\begingroup$

Here is an idea to do something less time consuming if $x$ randomly chosen, ie. not in $\mathbb{F}$ most of the time. It assumes that divisions by powers of 2 and additions are free compared to divisions by odd numbers, and tries to avoid them as much as possible.

  1. Compute how many times $x$ is divided by $2$, that is the max $p$ such as $x = 2^p*...$. That is a number of $0$ in binary mode

  2. Knowing p, find possible $n$, there are 0 or 2. I don't have a direct way to do that but it can be fast using properties such as if $n=2^k$ then $n!=2^{n-1} * (2k+1)$

  3. If you have 2 candidates $n$ and $n-1$, you can start to divide $x$ by $n-1$, the result by $n-2$ ... You may start by the big numbers because the odds are bigger to invalidate the candidates or by the small because it is cheaper. I don't know the best strategy here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.