How to solve factorial equations with very big numbers

Question

I have problem. I've calculated memory complexity of my algorithm. In exchange of very good time complexity of my algorithm, I have memory complexity $x!$, where $x$ is number of elements my algorithm gets.

Number of numbers I can easily store equals $2^{22000000}$. How many elements can my algorithm accept?

$x!=2^{22000000}$

How can I solve it? I've tried several calculators (even wolfram alpha), but no calculator was able to solve it. I've tried to use Stirling approximation ( Solving equations with factorials? ), but the number is just too big.

Do you know some online calculator that would be powerfull enough to calculate it? Or some other method to calculate it? I do not need exact number, I just want to know how big the number is (if I could tell number of digits in the number, it would be great).

Thanks, Peter

Answer 1

In this answer is given the approximation $$ n\sim e\exp\left(\operatorname{W}\left(\frac1{e}\log\left(\frac{n!}{\sqrt{2\pi}}\right)\right)\right)-\frac12 $$ Plugging in $n!=2^{22000000}$, we get $n\approx1175108.4$. Then $$ 1175108!\approx2^{21999991.937} $$ and $$ 1175109!\approx2^{22000012.101} $$

Answer 2

A quick and dirty approximation.

Considering the function $\log_2(x!)$ for $10^3 \leq x \leq 10^6$ (by steps of $10^3$) and considering a totally empirical model $a+b x^c$, a non linear regression gave $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -24230.2 & 415.912 & \{-25046,-23414\} \\ b & 6.22383 & 0.005670 & \{6.21271,6.23496\} \\ c & 1.07893 & 0.000065 & \{1.07880,1.07905\} \\ \end{array}$$ So, if $x!=2^k$, the solution will be $$x=0.183666 (k+24230.2)^{0.926847}$$ For $k=22 \times 10^6$, this would lead to $x=1.17429\times 10^6$ which is not too bad compared to gammatester's exact result.

Edit after robjohn's answer

Remembering that $z=W(z)\, e^{W(z)}$ and taking into account that equation $x!=2^k$ has to be solved for large values of $k$, we can make good approximations defining $$z=\frac{2k \log(2)-\log(2\pi)}{2e}\qquad L_1=\log(z)\qquad L_2=\log(L_1)$$ and use the truncated expansion given here to get $$x\approx \frac{e z} {L_1-L_2+\frac{L_2}{L_1}+\frac{L_2(L_2-2)}{2L_1^2}+\frac {L_2(6-9L_2+2L_2^2)}{6L_1^3}}-\frac 12$$ which, for $k=22 \times 10^6$, would lead to $x=1175102$. Adding the next terms of the given expansion would lead to more accurate values.