6
$\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$
4
  • 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$ Commented Sep 8, 2014 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$ Commented Sep 8, 2014 at 15:16
  • $\begingroup$ Related links within: math.stackexchange.com/questions/171882/… $\endgroup$ Commented Sep 8, 2014 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$ Commented Sep 10, 2014 at 9:00

2 Answers 2

Reset to default
9
$\begingroup$

Divide $x$ by $2$, then divide that result 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
  • 4
    $\begingroup$ This should read "then divide that result by $3$..." $\endgroup$ Commented Sep 8, 2014 at 14:56
  • 2
    $\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$ Commented Sep 8, 2014 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$ Commented Sep 10, 2014 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$ Commented Sep 10, 2014 at 11:25
6
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.