1
$\begingroup$

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.$$

$\endgroup$
3
  • $\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$ May 14, 2012 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, 2012 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, 2012 at 13:41

2 Answers 2

2
$\begingroup$

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})}$.
$\endgroup$
7
  • $\begingroup$ How to estimate $W(\cdot)$? $\endgroup$
    – John Smith
    May 14, 2012 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, 2012 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, 2012 at 15:06
  • $\begingroup$ I think it's complicated to compute $W_0(x)$. $\endgroup$
    – John Smith
    May 14, 2012 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, 2012 at 10:15
0
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ $\frac{a^i}{i!}<{a^i}$ seems too loose. What if Stirling's Approx. is applied? $\endgroup$
    – John Smith
    May 14, 2012 at 13:38
  • $\begingroup$ @JohnSmith: If you are programming, you can now just count downward in $i$ and check. $\endgroup$ May 14, 2012 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$ May 14, 2012 at 14:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .