Solving $x!=n$ without a calculator for large $n$

Solution 1:

For the solution of $x!=n$, @Gary proposed a superb approximation (have a look here)

$$x = \frac{{\log \left( {\frac{n}{{\sqrt {2\pi } }}} \right)}}{{W\left( {\frac{1}{e}\log \left( {\frac{n}{{\sqrt {2\pi } }}} \right)} \right)}} - \frac{1}{2}$$ where $W(.)$ is Lambert function.

Let us rewrite it as $$x=e \frac t{W(t)}-\frac{1}{2} \qquad \text{with} \qquad t=\frac 1e\log \left( {\frac{n}{{\sqrt {2\pi } }}} \right)$$

Now, for large values of $t$, use what is given in the Wikipedia page $$W(t) \sim L_1-L_2+\frac{L_2}{L_1}+\frac{L_2(L_2-2)}{2L_1^2}+\frac{L_2(2L_2^2-9L_2+6)}{6L_1^3}+\cdots$$ where $L_1=\log(t)$ and $L_2=\log(L_1)$

Using my $50+$ years old non-programmable pocket calculator for $$n=123456789876543212345678987654321234567898765432123456789$$ $$t=47.1756\qquad L_1=3.85388\qquad L_2=1.34908$$ Using only the first three terms, then $$W(t)\sim3.85388-1.34908+\frac{1.34908}{3.85388}=2.85485$$ $$x\sim e \frac{47.1756}{2.85485}-\frac 12=44.4188$$ while, as a real, the solution is $45.0083$.

Speaking about integers, for sure, you need to use $\lceil x \rceil$ and the results are the same. $$45!=119622220865480194561963161495657715064383733760000000000$$ $$46!=5502622159812088949850305428800254892961651752960000000000$$ Using the gamma function $$44.4188!=13053540092571206188366309387719398631004867852125601792$$ $$45.0083!=123456789876545254267360504092794809714819815437028556800$$

Solution 2:

Extending Henry's suggestion, we have any factor of 5 is going to be preceded by a factor of 2, so we can count the number of factors of 5 by counting the trailing 0's.

Every 5th 0 counts as two 5s, since those are multiples of 25. Every 25th 0 counts as 3 5s, etc. In other words, we just need to correct for the "overcounts" of 0s by things that have more than one factor of 5.

Thus, we know the largest the largest multiple of 5 is equal to or less than $x$ is given by letting $m$ equaling the number of trailing 0s in $n$ and solving for $r$ as follows: $$r:=\lfloor m/5 \rfloor + \lfloor m/5^2 \rfloor + \dots $$ Then we get $$5r\leq x<5(r+1) $$ This converges a lot faster than powers of 2 and then narrows your answer down to 5 possibilities. I'm not sure if there's a simple way to expressly state $x4$ in terms of $n$ beyond this range of 5 to check, but if you didn't need that, this converges fast enough and is easy enough to check the remaining numbers

Solution 3:

Just looking at the number of digits seems to provide an accurate solution for $x > 9$.

$\ln x! = \sum_{1 \le k\le x} \ln k \approx \int _{1}^{x+1} \ln x\,\mathrm dx + \frac12 \ln (x+1)=(x+\frac12) \ln (x+1) - x$

The error tends to a constant, and by numerical evidence it is around 0.1. Therefore one can just ignore it.

So converting to digits, $\log x! \approx (x+\frac12) \log (x+1) - \frac x{\ln 10}$. This should serve for most purposes.

For $x < 10$, recite the factorials.

Solution 4:

Integer binary algorithm

Assume that we have integer input $x!=n$

1. If $n=1$ return $1$
2. Count the number of trailing zeros, $t$, in the binary representation of $n$, trailing zeros are telling the highest $2^k$ number is divisible by, you do not need a full binary expansion
3. Calculate $w=\frac{n}{t!}$
4. Calculate the number of times $t+1$ divides $w$, rounded down to the nearest integer giving this result: $$r= \left \lfloor \frac{\ln(w)}{\ln(t+1)} \right \rfloor$$
5. Return $t+r$

Example:

$$2432902008176640000_{10}=10000111000011011001110111110010000010101101000000000000000000_2$$

Notice that in the practice you are not doing a full binary conversion, you just want to know if the number is divisible by $2,4,8,16,32,64,...$ i.e. $2^k$.

So start from:

$$\frac{2432902008176640000}{18!}=380$$

$$19^2<380<19^3$$

so $r=2$

so it is $2432902008176640000=(18+2)!=20!$

Notice that this method is giving you a very close value. You get for $100!$, $97$ already.

Dividing a large decimal number by 2.

1. Write above each odd digit $1$.
2. Decrement all odd digits by $1$.
3. Now divide each digit by $2$.
4. Add 5 to the digit that is to the right of $1$.

    8712364123019561232
    1.
     11 1  1 1 111 1 1 
    2.
    8602264022008460222
    3.
      55 5  5 5 555 5 5
    4301132011004230111
    4.
    4356182061509780616