Reverse factorial

Question

Well, we all know that if N is given it's easy to calculate N!. But what about the inverse?

N! is given and you are about to find N - Is that possible ? I'm curious.

Answer 1

Based on:

Full inverted factorial valid for x>1

Use the suggested calculation. If factorial is expressible in full binary form the algorithm is:

Suppose input is factorial x, x=n!

1. Return 1 for 1
2. Find the number of trailing 0's in binary expansion of the factorial x, let us mark it with t
3. Calculate x/fact(t), x divided by the factorial of t, mathematically x/(t!)
4. Find how many times x/fact(t) divides t+1, rounded down to the nearest integer, let us mark it with m
5. Return m+t

__uint128_t  factorial(int  n);

int invert_factorial(__uint128_t fact)
{
    if (fact == 1) return 1;

    int t = __builtin_ffs(fact)-1;
    int res = fact/factorial(t);

    return t + (int)log(res)/log(t+1);
}

128-bit is giving in on 34!

Answer 2

If you have Q=N! in binary, count the trailing zeros. Call this number J.

If N is 2K or 2K+1, then J is equal to 2K minus the number of 1's in the binary representation of 2K, so add 1 over and over until the number of 1's you have added is equal to the number of 1's in the result.

Now you know 2K, and N is either 2K or 2K+1. To tell which one it is, count the factors of the biggest prime (or any prime, really) in 2K+1, and use that to test Q=(2K+1)!.

For example, suppose Q (in binary) is

1111001110111010100100110000101011001111100000110110000000000000000000

(Sorry it's so small, but I don't have tools handy to manipulate larger numbers.)

There are 19 trailing zeros, which is

10011

Now increment:

1: 10100
2: 10101
3: 10110 bingo!

So N is 22 or 23. I need a prime factor of 23, and, well, I have to pick 23 (it happens that 2K+1 is prime, but I didn't plan that and it isn't needed). So 23^1 should divide 23!, it doesn't divide Q, so

N=22

Answer 3

Well, if you know that M is really the factorial of some integer, then you can use

n! = Gamma(n+1) = sqrt(2*PI) * exp(-n) * n^(n+1/2) + O(n^(-1/2))

You can solve this (or, really, solve ln(n!) = ln Gamma(n+1)) and find the nearest integer. It is still nonlinear, but you can get an approximate solution by iteration easily (in fact, I expect the n^(n+1/2) factor is enough).

Answer 4

inverse_factorial( X )
{
   X_LOCAL = X;
   ANSWER = 1;
   while(1){
      if(X_LOCAL / ANSWER == 1)
        return ANSWER;
       X_LOCAL = X_LOCAL / ANSWER;
       ANSWER = ANSWER + 1;
    }
}

Answer 5

Most numbers are not in the range of outputs of the factorial function. If that is what you want to test, it's easy to get an approximation using Stirling's formula or the number of digits of the target number, as others have mentioned, then perform a binary search to determine factorials above and below the given number.

What is more interesting is constructing the inverse of the Gamma function, which extends the factorial function to positive real numbers (and to most complex numbers, too). It turns out construction of an inverse is a difficult problem. However, it was solved explicitly for most positive real numbers in 2012 in the following paper: http://www.ams.org/journals/proc/2012-140-04/S0002-9939-2011-11023-2/S0002-9939-2011-11023-2.pdf . The explicit formula is given in Corollary 6 at the end of the paper.

Note that it involves an integral on an infinite domain, but with a careful analysis I believe a reasonable implementation could be constructed. Whether that is better than a simple successive approximation scheme in practice, I don't know.

Answer 6

C/C++ code for what the factorial (r is the resulting factorial):

int wtf(int r) {
    int f = 1;

    while (r > 1)
        r /= ++f;

    return f;
}

Sample tests:

Call: wtf(1)
Output: 1

Call: wtf(120)
Output: 5

Call: wtf(3628800)
Output: 10