Reverse factorial

Question

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

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

Answer 1

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.

Answer 2

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

Answer 3

int reverce_factorial( int factorial ){
  int current = 1;
  while ( factorial > current ){
    if ( factorial % current ) return -1;
    factorial /= current;
    current++;
  }
  if (factorial == current) return current;
  else return -1;      
}

Answer 4

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

Answer 5

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 6

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.

Answer 7

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.

Answer 8

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 9

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 10

Check inverse gamma functions from here http://functions.wolfram.com/GammaBetaErf/InverseGammaRegularized/ They have multiple aproximations

Answer 11

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'