16
$\begingroup$

I participated in an Estimathon (a speed contest of Fermi problems) not long ago. It works as follows. Contestants are given questions and they must give a closed range $[a,b]$ which should contain the correct answer. The scoring guidelines are such that you want to minimize your "number of points" where the points depends on $\left\lfloor\frac{b}{a}\right\rfloor$. If your range does not contain the correct answer, your number of points doubles which is bad. So the top priority is to make sure your range contains the correct answer. After that, it is important to make sure your range is not too big.

One of the questions was:

Estimate $100!$.

I was the only person among 40 people to get this correct, since I had memorized $100! \approx 9.33 \times 10^{157} $, so I just put $\left[9 \times 10^{157}, 10^{158}\right]$. However, is there a way to get this correct to one order of magnitude? Note that two orders of magnitude is too imprecise for this contest.

I was thinking of using Stirling's approximation but even that is quite tedious to do by hand (no calculators were allowed)!

$\endgroup$
  • 3
    $\begingroup$ There's Stirling's Formula: $n!\sim \sqrt{2\pi n}\left(n/e\right)^n$. $\endgroup$ – Robert Wolfe Aug 23 '14 at 1:55
  • 2
    $\begingroup$ Oh nice concept this, Estimathon. $\endgroup$ – Sawarnik Aug 28 '14 at 9:13
22
+50
$\begingroup$

What's wrong with Stirling's approximation? $$100!\approx \sqrt{2\pi 100}(100/e)^{100}\approx\sqrt{628}(100/e)^{100}$$ Since $628\approx 625$, the square root gives $\approx25$, and now: $$(100/e)^{100}=100^{100} e^{-100}= 100^{100} 10^{-100 /\ln 10}$$ Now if you memorized $100!$, surely you memorized $\ln 10 \approx 2.3$, so: $$100!\approx 2.5 \cdot 10^{157}$$ Which is correct to within an order of magnitude, without using a calculator.

Addendum: If you note that $100/2.3$ is around $43.5$, and use $\sqrt{10}\approx 3.2$, you get $8 \cdot 10^{157}$, which is even closer.

$\endgroup$
  • 1
    $\begingroup$ Whoah, I think I misremembered Stirling's approximation or something like that $-$ on the day of the contest, for some reason, I came up with stuff that takes several several minutes to do by hand. $\endgroup$ – Ahaan S. Rungta Aug 23 '14 at 2:24
  • 3
    $\begingroup$ This is clearly what is intended for the problem. Getting something of order $10^{157}$ within an order of magnitude is amazing. Douglas Hofstadter has stated that in this range we are estimating the power of $10$, so getting within $1$ of $157$ is great. $\endgroup$ – Ross Millikan Aug 23 '14 at 5:14
  • $\begingroup$ @RossMillikan. I wonder how people are able to remember numbers like that ! Really amazing. $\endgroup$ – Claude Leibovici Aug 23 '14 at 15:10
4
$\begingroup$

If you are good in memoralization, then it is very elegant to use one of Ramanujan's factorial approximations. In Ramanujan's lost notebook you can find this one:

$$ n! \sim \sqrt{\pi}n^{n}e^{-n}\sqrt[6]{8n^3+4n^2+n+\frac{1}{30}} $$

This is a very strong, and also famous approximation. Using it for approximate $100!$ you get $9.3326215444826261629 \cdot 10^{157}$. The first $10$ digit is correct! If you are intrested in factorial approximation you can get some result here.

Edit. This might be interesting.

$\endgroup$
1
$\begingroup$

I am not at all familiar with this type of contest, so forgive me if this is stupid.

Assuming that you have a programmable calculator, you could first compute in a loop $$A=\log_{10}(100!)=\sum_{i=1}^{i=100}\log_{10}(i)\simeq 157.9700037\simeq158-0.03$$ So, $$10^A=100!\simeq10^{158}10^{-0.03}=e^{-0.03 log (10)}10^{158}\simeq e^{-0.069} 10^{158}$$ Now, use one term of the Taylor expansion of $e^x$ around $x=0$ to get $e^{-0.069}\simeq 0.931$ which corresponds to an underestimate. Then $$0.931 \times 10^{158} \lt 100! \lt 10^{158}$$

$\endgroup$
  • 1
    $\begingroup$ The OP rather specifically noted that "no calculators were allowed", but nice method anyway. $\endgroup$ – nbubis Aug 23 '14 at 7:53
  • $\begingroup$ @nbubis. Ooops ! I am sorry, I missed it ! In my answer, I even wrote "Assuming that you have a programmable calculator" !! Cheers :-) $\endgroup$ – Claude Leibovici Aug 23 '14 at 15:08

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.