Given two real numbers $0<a<1$ and $0<\delta<1$, I want to find a positive integer $i$ (it is better to a smaller $i$) such that $$\frac{a^i}{i!} \le \delta.$$

  • $\begingroup$ Are you sure you want the minimum $i$ which will be hard to compute exactly? Or would you be happy with an $N$ such that any $i$ greater than $N$ would work (which is what you would need if you were looking at problem with limits). $\endgroup$ – Mark Bennet May 14 '12 at 11:15
  • $\begingroup$ If the minimum $i$ is too hard to find, then it is better to find an integer $i$ as small as possible $\endgroup$ – John Smith May 14 '12 at 11:18
  • $\begingroup$ @draks, how to use Lambert-W-function? I am now obtaining the following inequality: $${(a\cdot e)}^i<\sqrt{2\pi}\delta i^{i+1/2}$$ $\endgroup$ – John Smith May 14 '12 at 13:41

Here is what I put together from my math toy box:

  1. Use Stirling's approximation $i!\approx(i/e)^i$ to get $\left( \frac{ae}{i}\right)^i \le \delta$.
  2. Call $ae=1/b$ and invert to get $(ib)^i\ge \delta^{-1}$.
  3. Continue with $(ib)^{ib}\ge \delta^{-b}$, define $x:=bi$ to get $x^x\ge\delta^{-b}$
  4. and then use $$ x\ge\frac{\ln(\delta^{-b})}{W(\ln \delta^{-b})}=\frac{\ln(\delta^{-1/ae})}{W(\ln \delta^{-1/ae})}. $$
  5. Resubstitute $x=\frac{i}{ae}$ for the result $i\ge\frac{ae\ln(\delta^{-1/ae})}{W(\ln \delta^{-1/ae})}$.
  • $\begingroup$ How to estimate $W(\cdot)$? $\endgroup$ – John Smith May 14 '12 at 15:03
  • $\begingroup$ @JohnSmith, would the Asymptotic expansion $W_0 (x) = \sum_{n=1}^\infty \frac{(-n)^{n-1}}{n!}\ x^n = x - x^2 + \frac{3}{2}x^3 - \frac{8}{3}x^4 + \frac{125}{24}x^5 - \cdots $ work for you? $\endgroup$ – draks ... May 14 '12 at 15:05
  • $\begingroup$ Also, $i! \sim {(i/e)}^i$ doesn't mean $i! \ge {(i/e)}^i$. This problem can be easily fixed by using the upper bound of $i!$ of Stirling Approx., but how to calculate $W(\cdot)$ is a very important issue. $\endgroup$ – John Smith May 14 '12 at 15:06
  • $\begingroup$ I think it's complicated to compute $W_0(x)$. $\endgroup$ – John Smith May 14 '12 at 15:11
  • 1
    $\begingroup$ Ask your favorite math knowlegde base and get this: $\displaystyle \log x - \log \log x + \frac{1}{2}\frac{{\log \log x}}{{\log x}} \le W(x) \le \log x - \log \log x + \frac{e}{{e - 1}}\frac{{\log \log x}}{{\log x}}$. Does that help? $\endgroup$ – draks ... May 16 '12 at 10:15

Here is a not-very-good answer. Let $i$ be the result of rounding $\log\delta/\log a$ up to the nearest integer. Then $i\ge\log\delta/\log a$, so $i\log a\le\log\delta$ (remember, $\log a\lt0$), so $a^i\le\delta$, so $a^i/i!\le\delta$.

  • $\begingroup$ $\frac{a^i}{i!}<{a^i}$ seems too loose. What if Stirling's Approx. is applied? $\endgroup$ – John Smith May 14 '12 at 13:38
  • $\begingroup$ @JohnSmith: If you are programming, you can now just count downward in $i$ and check. $\endgroup$ – Ross Millikan May 14 '12 at 14:01
  • $\begingroup$ @JohnSmith: Stirling doesn't buy you much here: you will get i both in the base and in the exponent. $\endgroup$ – Johannes Kloos May 14 '12 at 14:07

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.