Finding $n$ in $n=ReverseFactorial(x)$ where $x$ is known.

Question

My software application receives a series of very large integers (hundreds of decimal digits). So far, I have been using string/textual representation of decimal digits for very simple manipulation (calculating on the number of digits, etc.).

I want to find the highest $n$ in $n=ReverseFactorial(x)$ where $x$ is the big integer I already have. Examples of expected results would be:

• $4=ReverseFactorial(24)$
• $4=ReverseFactorial(25)$
• $4=ReverseFactorial(119)$
• $5=ReverseFactorial(120)$
• $5=ReverseFactorial(719)$
• $6=ReverseFactorial(720)$

I can convert $x$ into its respective decimal or binary notation if either of those number systems could help in calculating $n$ very fast. As an example, finding the base 2 log for a very large number is possible by inspecting the most significant bit. Is there such a solution for factorials? Could the number of digits provide a clue?

UPDATE: Based on ShreevatsaR's answer, it appears that if the number to be tested is not an exact factorial (which it is not in my case), there is no efficient way to determine $n$. I wanted to verify this here so I can move on to other ways of addressing my context.

Answer 1

You can use Stirling's approximation $n! \approx \left(\frac ne \right)^n\sqrt {2\pi n}, \log n! \approx n(\log n -1)+1.838 +\frac 12 \log n$ and iteration: start with $n_0=\log x,$ then $n_1=\frac {\log x}{\log n_0}$ will bracket the root. Use you favorite root finder, which should converge quickly.

Answer 2

I don't think there is a problem even if the number is not an exact factorial.

Here is how to solve the problem:

by definition: $$ n! = n \times (n-1) \times ..... \times 2 \times 1$$

here is how to get n if you have x:

start by dividing by 2, there are three cases:

1. we get a number greater than 1, in this case keep dividing by 3,4,5... until you reach something smaller than or equal 1. see the two cases below:

   2.we get exactly 1, this is what we want, in this case the last number we divided by is n.

   1. we get something less than 1, in this case we have to get back one step i.e n = last number we divided by - 1.

example:

let us take the number 719, start by dividing by 2:

$\frac{719}{2} = 359.5$ --> still greater than 1
$\frac{395.5}{3} = 119.83$ --> still greater than 1
$\frac{119.83}{4} = 29.9575$ --> still greater than 1
$\frac{29.9575}{5} = 5.9915$ --> still greater than 1
$\frac{5.9915}{6} = 0.998$ --> less than 1
we should get back to the previous number i.e n=5.

Here is a simple function in c to do this:

  long reverse(unsigned long long x)
{
long i;
double n;
n=x;
for(i=2; n>1;i++)
   {
    n= n/i;

    if(n == 1)
    return i;
    else if(n < 1)

        return i-1;


   }
 }