Reverse factorial

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 开发者_StackOverflow中文版are about to find N - Is that possible ? I'm curious.

---

1. Set X=1.
2. Generate F=X!
3. Is F = the input? If yes, then X is N.
4. If not, then set X=X+1, then start again at #2.

You can optimize by using the previous result of F to compute the new F (new F = new X * old F).

It's just as fast as going the opposite direction, if not faster, given that division generally takes longer than multiplication. A given factorial A! is guaranteed to have all integers less than A as factors in addition to A, so you'd spend just as much time factoring those out as you would just computing a running factorial.

---

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

---

int inverse_factorial(int factorial){
    int current = 1;
    while (factorial > current) {
        if (factorial % current) {
            return -1; //not divisible
        }
        factorial /= current;
        ++current;
    }
    if (current == factorial) {
        return current;
    }
    return -1;
}

---

Yes. Let's call your input x. For small values of x, you can just try all values of n and see if n! = x. For larger x, you can binary-search over n to find the right n (if one exists). Note hat we have n! ≈ e^(n ln n - n) (this is Stirling's approximation), so you know approximately where to look.

The problem of course, is that very few numbers are factorials; so your question makes sense for only a small set of inputs. If your input is small (e.g. fits in a 32-bit or 64-bit integer) a lookup table would be the best solution.

(You could of course consider the more general problem of inverting the Gamma function. Again, binary search would probably be the best way, rather than something analytic. I'd be glad to be shown wrong here.)

Edit: Actually, in the case where you don't know for sure that x is a factorial number, you may not gain all that much (or anything) with binary search using Stirling's approximation or the Gamma function, over simple solutions. The inverse factorial grows slower than logarithmic (this is because the factorial is superexponential), and you have to do arbitrary-precision arithmetic to find factorials and multiply those numbers anyway.

For instance, see Draco Ater's answer for an idea that (when extended to arbitrary-precision arithmetic) will work for all x. Even simpler, and probably even faster because multiplication is faster than division, is Dav's answer which is the most natural algorithm... this problem is another triumph of simplicity, it appears. :-)

---

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).

---

Multiple ways. Use lookup tables, use binary search, use a linear search...

Lookup tables is an obvious one:

for (i = 0; i < MAX; ++i)
    Lookup[i!] = i; // you can calculate i! incrementally in O(1)

You could implement this using hash tables for example, or if you use C++/C#/Java, they have their own hash table-like containers.

This is useful if you have to do this a lot of times and each time it has to be fast, but you can afford to spend some time building this table.

Binary search: assume the number is m = (1 + N!) / 2. Is m! larger than N!? If yes, reduce the search between 1 and m!, otherwise reduce it between m! + 1 and N!. Recursively apply this logic.

Of course, these numbers might be very big and you might end up doing a lot of unwanted operations. A better idea is to search between 1 and sqrt(N!) using binary search, or try to find even better approximations, though this might not be easy. Consider studying the gamma function.

Linear search: Probably the best in this case. Calculate 1*2*3*...*k until the product is equal to N! and output k.

---

If the input number is really N!, its fairly simple to calculate N.

A naive approach computing factorials will be too slow, due to the overhead of big integer arithmetic. Instead we can notice that, when N ≥ 7, each factorial can be uniquely identified by its length (i.e. number of digits).

• The length of an integer x can be computed as log10(x) + 1.
• Product rule of logarithms: log(a*b) = log(a) + log(b)

By using above two facts, we can say that length of N! is:

which can be computed by simply adding log10(i) until we get length of our input number, since log(1*2*3*...*n) = log(1) + log(2) + log(3) + ... + log(n).

This C++ code should do the trick:

double result = 0;
for (int i = 1; i <= 1000000; ++i) {  // This should work for 1000000! (where inputNumber has 10^7 digits)
    result += log10(i);
    if ( (int)result + 1 == inputNumber.size() ) {    // assuming inputNumber is a string of N!
        std::cout << i << endl;
        break;
    }
}

(remember to check for cases where n<7 (basic factorial calculation should be fine here))

Complete code: https://pastebin.com/9EVP7uJM

---

Here is some clojure code:

(defn- reverse-fact-help [n div]
    (cond (not (= 0 (rem n div))) nil
          (= 1 (quot n div)) div
          :else (reverse-fact-help (/ n div) (+ div 1))))
(defn reverse-fact [n] (reverse-fact-help n 2))

Suppose n=120, div=2. 120/2=60, 60/3=20, 20/4=5, 5/5=1, return 5

Suppose n=12, div=2. 12/2=6, 6/3=2, 2/4=.5, return 'nil'

---

int p = 1,i;
//assume variable fact_n has the value n!
for(i = 2; p <= fact_n; i++) p = p*i;
//i is the number you are looking for if p == fact_n else fact_n is not a factorial

I know it isn't a pseudocode, but it's pretty easy to understand

---

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;
    }
}

---

This function is based on successive approximations! I created it and implemented it in Advanced Trigonometry Calculator 1.7.0

double arcfact(double f){
 double result=0,precision=1000;
 int i=0;
 if(f>0){
   while(precision>1E-309){
     while(f>fact(result+precision)&&i<10){
 result=result+precision;
 i++;
   }
   precision=precision/10;
   i=0;
  }
  }
  else{
result=0;
   }
   return result;
 }

---

If you do not know whether a number M is N! or not, a decent test is to test if it's divisible by all the small primes until the Sterling approximation of that prime is larger than M. Alternatively, if you have a table of factorials but it doesn't go high enough, you can pick the largest factorial in your table and make sure M is divisible by that.

---

In C from my app Advanced Trigonometry Calculator v1.6.8

    double arcfact(double f) {
        double i=1,result=f;
        while((result/(i+1))>=1) {
            result=result/i;
            i++;
        }
        return result;
    }

What you think about that? Works correctly for factorials integers.

---

Simply divide by positive numbers, i.e: 5!=120 ->> 120/2 = 60 || 60/3 = 20 || 20/4 = 5 || 5/5 = 1

So the last number before result = 1 is your number.

In code you could do the following:

number = res
for x=2;res==x;x++{
    res = res/x

} 

or something like that. This calculation needs improvement for non-exact numbers.

---

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.

---

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

---

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!