16
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ If a is not divisible by 10 then you can get the number of 5's in n! by the value of k. $\endgroup$ – user94300 Jun 21 '15 at 8:49
  • $\begingroup$ Could you please elaborate ? Thanks. $\endgroup$ – Claude Leibovici Jun 21 '15 at 8:50
  • $\begingroup$ 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. $\endgroup$ – user94300 Jun 21 '15 at 8:54
  • $\begingroup$ 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? $\endgroup$ – wythagoras Jun 21 '15 at 9:19
  • $\begingroup$ @wythagoras. This is just to make the problem continuous. For sure the solution is $1402$. I just use Gamma for the Newton step. $\endgroup$ – Claude Leibovici Jun 21 '15 at 9:21
17
$\begingroup$

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$

$\endgroup$
17
  • 1
    $\begingroup$ I just finished a huge testing of your solution : I shall not ask you to guess what. It works like a charm ! Thanks again. $\endgroup$ – Claude Leibovici Dec 31 '16 at 14:04
  • 1
    $\begingroup$ 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. $\endgroup$ – robjohn♦ Dec 31 '16 at 14:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Claude Leibovici Jan 1 '17 at 5:54
  • 1
    $\begingroup$ $\unicode{x1F389}\unicode{x1F38A}\unicode{x1F55B}\unicode{x1F4A5}\unicode{x1F37E}$ Happy New Year!! I just found David Cantrell's post $\endgroup$ – robjohn♦ Jan 1 '17 at 7:19
  • 1
    $\begingroup$ More I see and use this answer, more I think it could be worth to publish it for the general solution of $a^n\,n!=k$ which could write $$n=\frac{1}{2} \left(\frac{\log \left(\frac{a k^2}{2 \pi }\right)}{W\left(\frac{a \log \left(\frac{a k^2}{2 \pi }\right)}{2 e}\right)}-1\right)$$ $\endgroup$ – Claude Leibovici Nov 9 '17 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.