# Could this approximation be made simpler ? Solve $n!=a^n 10^k$

I need to find the smallest value of $n$ such that $$\frac{a^n}{n!}\leq 10^{-k}$$ in which $a$ and $k$ are given (these can be large numbers).

I set the problem as : solve for $n$ the equation $$n!=a^n\, 10^k$$ I used for $n!$ Stirling approximation in which I ignored the $\sqrt n$ term. This gives an upper bound of the solution I rewrote as $$n_0=a\,e\, \frac A {W(A)}$$ $W$ being Lambert function and $$A=\frac{k \log (10)- \log (\sqrt{2 \pi} )}{a\,e }$$ which is not too bad (for example, using $k=1000$, $a=100$, the approximation gives $n_0\approx 1402.65$, the algebraic solution being $n\approx 1401.27$).

At this point, I could go backwards and find the solution. This is what I should call brute force.

For sure, starting from this estimate $n_0$, I could perform one iteration of Newton method and get $$n_1=n_0-\frac{\log (\Gamma (n_0+1))-(n_0 \log (a)+k \log (10))}{\psi (n_0+1)-\log (a)}$$ which is still an upper bound (Darboux theorem). Similarly, I could do the same using Stirling approximation and get $$n_1=n_0-\frac{\left(n_0+\frac{1}{2}\right) \log (n_0)-n_0 (1+\log (a))-k \log (10)+ \log (\sqrt{ 2 \pi })}{\frac{1}{2 n_0}+\log (n_0)-\log (a)}$$

However, using the rigorous formulation, this makes the second calculation quite expensive for little improvement and I wonder if something simpler could be considered.

Edit

It is sure that for a given value of $k$, the problem would be much simpler since I could perform a least square fit for a model $$n=\frac{\alpha}{W\big(\frac{\beta}a\big)}$$ and the results are quite good; for example, if $k=1000$, $\alpha=2298.64$, $\beta=845.965$ (to be compared to $\alpha_0=2301.67$ and $\beta_0=846.736$ from the initial model). For $a=100$, this would give $n=1401.28$ which is the answer. The problem is that many $k$'s have to be considered and curve fit does not look to be a solution.

• If a is not divisible by 10 then you can get the number of 5's in n! by the value of k. – user94300 Jun 21 '15 at 8:49
• Could you please elaborate ? Thanks. – Claude Leibovici Jun 21 '15 at 8:50
• If k is 10, then we know that the number 5 comes 10 times in n!. Hence n is between 45 and 49 (including both). It can be a start. – user94300 Jun 21 '15 at 8:54
• You have $n \approx 1401.27$, but you also have $n!$. Does this mean you want to to use the Gamma function rather than the factorial? – wythagoras Jun 21 '15 at 9:19
• @wythagoras. This is just to make the problem continuous. For sure the solution is $1402$. I just use Gamma for the Newton step. – Claude Leibovici Jun 21 '15 at 9:21

## 1 Answer

Stirling's Formula says $$\log\left(\frac{a^n}{n!}\right) \sim -n\log\left(\frac n{ea}\right)-\frac12\log(2\pi n)\tag{1}$$ Multiplying by $-\frac1{ea}$ and subtracting $\frac1{2ea}\log(2\pi ea)$, we get \begin{align} -\frac1{ea}\log\left(\frac{a^n}{n!}\sqrt{2\pi ea}\right) &\sim\frac{n}{ea}\log\left(\frac n{ea}\right)+\frac1{2ea}\log\left(\frac n{ea}\right)\\ &=\frac{n+\frac12}{ea}\log\left(\frac n{ea}\right)\\ &\approx\frac{n+\frac12}{ea}\log\left(\frac{n+\frac12}{ea}\right)-\frac1{2ea}\tag{2} \end{align} Applying the Lambert W Function to $(2)$ gives $$n\sim ea\exp\left(\operatorname{W}\left(-\frac1{ea}\log\left(\frac{a^n}{n!}\sqrt{2\pi a}\right)\right)\right)-\frac12\tag{3}$$ Plugging in $\log\left(\frac{a^n}{n!}\right)=-k\log(10)$ yields $$\bbox[5px,border:2px solid #C0A000]{n\sim ea\exp\left(\operatorname{W}\left(\frac k{ea}\log(10)-\frac1{2ea}\log(2\pi a)\right)\right)-\frac12}\tag{4}$$ For $k=1000$ and $a=100$, $(4)$ gives $1401.274188$

• This is an elegant and beautiful solution for sure ! – Claude Leibovici Dec 31 '16 at 8:38
• I just finished a huge testing of your solution : I shall not ask you to guess what. It works like a charm ! Thanks again. – Claude Leibovici Dec 31 '16 at 14:04
• You're welcome! I'm glad it works well. Other than Stirling, about the only approximation was $\log\left(1+\frac1{2n}\right)\approx\frac1{2n}$. There's not much to add inaccuracy. – robjohn Dec 31 '16 at 14:17
• Happy New Year !. I suppose that you noticed that, setting $a=1$ your formule gives the inverse gamma function and the formula is very close to what Cantrell proposed. – Claude Leibovici Jan 1 '17 at 5:54
• $\unicode{x1F389}\unicode{x1F38A}\unicode{x1F55B}\unicode{x1F4A5}\unicode{x1F37E}$ Happy New Year!! I just found David Cantrell's post – robjohn Jan 1 '17 at 7:19