Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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). –  Mark Bennet May 14 '12 at 11:15
    
If the minimum $i$ is too hard to find, then it is better to find an integer $i$ as small as possible –  John Smith May 14 '12 at 11:18
2  
Twenty percent accept rate? Don't you like the answers you're getting on this website? –  Gerry Myerson May 14 '12 at 12:39
1  
You could use Stirling's Approximation to $i!$ and then try to invoke the Lambert-W-function? Would this be ok, for you? and I totally agree with Gerry's comment... –  draks ... May 14 '12 at 12:40
    
@GerryMyerson and draks, of course I like most of the mathematicians answer, but haven't accepted yet because of a newcomer. Now my acceptance rate is increased. So could you give me a hand if you have some ideas? Thanks! –  John Smith May 14 '12 at 12:54
show 1 more comment

2 Answers

up vote 1 down vote accepted

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})}$.
share|improve this answer
    
How to estimate $W(\cdot)$? –  John Smith May 14 '12 at 15:03
    
@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? –  draks ... May 14 '12 at 15:05
    
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. –  John Smith May 14 '12 at 15:06
    
I think it's complicated to compute $W_0(x)$. –  John Smith May 14 '12 at 15:11
1  
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? –  draks ... May 16 '12 at 10:15
show 2 more comments

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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