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

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

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