How could we manually approximate $\sum_{i=1}^{50} i! = 3.1035 \times 10^{64}$?

How could we manually approximate $$\sum_{i=1}^{50} i!$$ to the value $3.1035 \times 10^{64}$?

I faced this question in my aptitude test,there were four option given,I couldn't solve it during the test,in home I used Stirling's approximation with wolfram's Mathematica to identify the correct option (if I did it right),however I am interested to know if there is any way we could do this entirely manually (probably using some tricks)?

PS:By manually I mean purely and only with pencil and paper.

$1)3.1035 \times 10^{65} \quad\quad 2) 3.1035 \times 10^{64} \quad\quad 3) 3.1035\times 10^{62} \quad\quad 4) 3.3339 \times 10^{62}$

-
Can we see what the other options were? – Henning Makholm Sep 17 '11 at 19:51
@Henning Makholm:I have added them. – Quixotic Sep 17 '11 at 19:56

The largest term in the sum is 50 times as large as the next largest, and $49\times50$ times as large as the second largest, and so forth. So to get just within a factor of 10, computing $50!$ alone ought to suffice.

But how manually is "manually" here? Is it purely pencil-and-paper, or do you have some way to compute logs and exponentials?

(Edit: Pencil and paper!) Here's a suggestion, assuming that one is a walking encyclopedia of mathematical trivia. With the given options it is (we hope) enough to compute $\log_{10} 50!$ to a precision of about $0.5$.

Assume that we remember Stirling's formula: $$\ln n! \approx \frac{\ln(2\pi)}2+\left(n+\frac12\right)\ln n - n$$ This gives $$\log n! = \frac{\log(2\pi)}2+\left(n+\frac 12\right)\log n - \frac{n}{\ln 10}$$

Assume that we know that $\log_{10} 5\approx 0.7$ and also assume that we know that $\ln 10\approx 2.3$. I don't think it is fair to assume we remember $\log_{10}(2\pi)$, but one easily sees it must be somewhere between 0.7 and 1, so let's conservatively set $\frac{\log(2\pi)}2\approx 0.4\pm 0.1$. We then get $$\log 50! \approx 0.4 \pm 0.1 + 50.5\times1.7 - \frac{50}{2.3}$$ which is pencil-and-paper tractable and works out to $$\log 50! \approx 64.55\pm 0.1$$ This should give some confidence in the $3\times10^{64}$ option .

-
purely pencil and paper! – Quixotic Sep 17 '11 at 19:50
Since $\pi\cong\sqrt{10}$ is a pretty good approximation, you can estimate $\log 2\pi$ fairly closely as $\log 2\sqrt{10}\cong 0.30103+0.5\cong 0.8$; the rounding errors even partly cancel. (Doesn’t everyone know $\log 2$ to $5$ places? :-)) – Brian M. Scott Sep 17 '11 at 21:38

Given those four choices, I can make a very good guess using only information that I have in memory and pencil-and-paper calculation.

$50 \ln 50 - 49 = \int\limits_1^{50}\ln x dx < \sum\limits_{n=1}^{50}\ln n < \int\limits_1^{51}\ln x dx = 51 \ln 51 - 50$. $\ln 10 \cong 2.3$, and $\log_{10} 5 \cong 0.7$, so $\ln 50 = \log_{10} 50 \ln 10 \cong 1.7\cdot 2.3 = 3.91$. $50\cdot 3.91 - 49 = 146.5$, and $51 \cdot 3.91 - 50 = 149.41$, so $\log_{10} 50!$ ought to be between about $\dfrac{146.5}{2.3} \cong 63.7$ and about $\dfrac{149.41}{2.3} \cong 65.0$. That pretty much pins it down to the second alternative.

(Had I not independently remembered that $\ln 10 \cong 2.3$, I could have got it from remembering that $e^3 \cong 20$ and $\ln 2 \cong 0.7$.)

-
Where did that very first 49 come from? – tzs Sep 18 '11 at 3:49
@tzs: $\int_1^a\ln x dx=[x\ln x - x]_1^a=a\ln a - a+1$. – Brian M. Scott Sep 18 '11 at 6:07

The final answer will be dominated by the largest term. Write the series as

$$50! + 49! +\cdots + 1!$$

$$50!(1+ \frac{1}{50}+ \frac{1}{49\cdot 50}+\cdots +\frac{1}{50!})$$

The numerical values of each of the subsequent terms decreases pretty quickly. So you can truncate the sum appropriately according to the number of decimal places you require. If you take just the first three terms, i.e $$\approx 50! \times 1.0204 = 3.1034 \times 10^{64}$$

You would need to calculate 50!, for which the only way I know is to use Stirling's formula. (In this test, were you provided logarithm tables?)

-
No we are likely to be provided with only a pencil and some scratch paper. – Quixotic Sep 18 '11 at 19:30

(This should be a comment since I'm not going to actually solve the problem, but it got too long)

Once you realize that the first term dominates, it comes down to estimating 50!. Now here is where you use test psychology. Choices 3 and 4 are pretty close together. You'd need a pretty good estimate to tell them apart. Tentatively conclude that it probably is not either of those.

That leaves choices 1 and 2. They differ by a factor of 10, so you can be pretty sloppy and still distinguish between them. It wouldn't actually take too long to just go ahead and multiply it out. If you take advantage of the prime factorization of the terms most of the multiplications will be by single digits which you can do in your head and just write down the result.

Someone more clever than I could probably first arrange 2, 3, ..., 50 into groups or arrange their factors into groups that multiply out into particularly easy numbers to work with (for instance pair up groups of 2 and 5 to work with) or to keep the error bounds reasonable, but I'd just go for brute force.

-
"Just multiplying them out" sounds rather daunting when the final product has 52 digits excluding trailing zeroes. Okay, one can probably get away with working to 3 or 4 significant digits in a balanced tree of multiplications, but that is still quite a lot of work. @Fool, how much time did you have for this? – Henning Makholm Sep 17 '11 at 22:14
I just tried it. It took about 15 minutes, and I ended up under the correct answer by about a factor of 3, so of the four choices given I would gave picked the right one. This was usually keeping 2 or 3 digits, and without much planning to try to control error. I wonder if this originates on an old exam. Calculation by hand was a lot more common at one time, and I suspect people were more adept at it. – tzs Sep 17 '11 at 23:54