# 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 are about to find N - Is that possible ? I'm curious.

-
Try MathOverflow. – Paddy Apr 16 '10 at 11:35
@Paddy: no, that's only for research-level math. This fits well here in my opinion. – IVlad Apr 16 '10 at 11:38
If you check the book Concrete Mathematics, I believe this is one of the discrete functions that Knuth extends into the continuous realm. Thus you could have inverse_fact(121) = 5.0001 or whatever is that actual value such that x!=121. I realize factorial is an integer function, in this book Knuth extends discrete (i.e., integer) functions to the continuous. I think that such an extension is the only sensible way for the OP's question; otherwise there are only a few valid inputs. – Heath Hunnicutt Jul 5 '10 at 16:51
@Heath: sounds like inverse gamma function. – JoshD Oct 27 '10 at 0:36

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.

-
I smell infinite loop :) – Petr Peller Apr 16 '10 at 11:39
Assuming the given input is actually a factorial, the loop will terminate eventually. If it's not, then the strict interpretation of my pseudocode would loop infinitely, but that's easily fixed by adding a `<` check instead. – Amber Apr 16 '10 at 11:41
That was actually what I was meaning, Franz - a check on `input < F` to terminate with no result. :P – Amber Apr 16 '10 at 11:44
Concerning infinite loop: I think most stackoverflow readers are able to modify the algorithm that an infinite loop can be exluded. – phimuemue Apr 18 '10 at 17:22
If you're able to pass in the end factorial, then you'll find it before hitting overflow. – Amber Apr 20 '10 at 4:09
``````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;
}
``````
-
yes, but why the float datatype? :) – Marek Apr 16 '10 at 11:46
Not anymore. I was thinking how to make it check, if `factorial` is not factorial of any number actually. – Draco Ater Apr 16 '10 at 11:48
You don’t need to go down to `factorial == 1`. You can stop when `factorial == current`. – Debilski Apr 16 '10 at 11:49
Works well only in cases where you can use a lookup table instead. (-1) – Pavel Shved Apr 16 '10 at 11:57
@ShreevatsaR Thanks! fixed – Draco Ater Apr 16 '10 at 12:02

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
``````
-
+1 for coming up with an actual algorithm – RCIX Apr 22 '10 at 5:57
"..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" - here to what should the 1's be added and whats the 'result' ? Could you please clarify it with say Q=120 . Thanks – pranay Feb 23 '12 at 5:37
@pranay: Q=1111000, three trailing zeroes. Three is 11, increment 11->100, I've incremented one time and there's one '1', so I stop. The result is 100, which is four, so N is four or five. I test five by counting the factors of 5 in Q, and sure enough Q=5! – Beta Feb 25 '12 at 2:48
@Beta: thanks for the explanation :) – pranay Feb 25 '12 at 13:13

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

-

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

-

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

-

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;
while(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;
}
``````
-
This assumes you have a `fact` function which accepts double arguments. – Teepeemm Jul 28 '15 at 18:01

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.

-

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

-

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.

-

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:

``````>>> wtf(1)
1
>>> wtf(120)
5
>>> wtf(3628800)
10
``````
-

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.

-
I would be very surprised if using the Gamma function was going to be an easy solution, let alone easier than other proposed solutions – GuyGreer Jul 31 '15 at 1:25
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/2652536/reverse-factorial/2652547", "fetch_time": 1462225801000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2016-18/segments/1461860117783.16/warc/CC-MAIN-20160428161517-00091-ip-10-239-7-51.ec2.internal.warc.gz", "warc_record_offset": 278407007, "warc_record_length": 28362, "token_count": 3239, "char_count": 11414, "score": 3.5, "int_score": 4, "crawl": "CC-MAIN-2016-18", "snapshot_type": "latest", "language": "en", "language_score": 0.9241259098052979, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00012-of-00064.parquet"}