Calculating without electricity

A transformer in my neighborhood blew sometime in the night and my electricity was off this morning. I thought about the post I wrote last night and how I could have written it without electricity.

Last night’s post included an example that if n = 8675309, n! has 56424131 digits, and that the last 2168823 digits are zeros. The previous post shows how you could compute the number of trailing zeros by hand. This post how you might compute the number of digits in n! by hand using only copy of Abramowitz and Stegun (A&S).

As shown here, the number of digits in n! is given by

⌊log10 n! ⌋ + 1

which you could compute in Python as

    floor( gammaln(n+1)/log(10.0) ) + 1

A&S has tables of the log gamma function, but only for integer arguments up to 100. You’re not going to compute log gamma of 8675310 that way. Instead, you’d want to use Stirling’s approximation

log n! ≈ (n + 1/2) log(n+1) – n – 1 + log(2π)/2.

Now we’re after the log base 10 of Γ(n + 1), which we could compute by finding the natural log and dividing by the natural of 10, as we did in the Python code above. But we could save a division by making a log base 10 version of Stirling’s approximation:

log10 n! ≈ (n + 1/2) log10 (n+1) – (n+1) log10(e) + log10(2π)/2

We can look up logarithms base 10 of e, 2, and π in A&S on pages 2 and 3. The hard part is computing the log base 10 of 8675310.

A&S has tables of logarithms base 10 (“common logarithms”) for integer arguments up to 1350. We can find on page 98 that

log10 867 = 2.9380190975
log10 868 = 2.9385197252

We could linearly interpolate between these to estimate

log10 867.5310 ≈ 2.9380190975 + 0.5310(2.9385197252 – 2.9380190975) = 2.9382849308

and so

log10 8675310 ≈ 4 + 6.9382849308 = 6.9382849308.

Now we have all we need to estimate log10 Γ (8675310) as

8675909.5 * 6.9382849308 – 8675310 * 0.4342944819 + 0.5*(0.3010299957 + 0.4971498727) = 56428293.28.

From this we estimate that n! has 56428294 digits. The exact answer is 56424131, so our answer is correct to four significant figures.

One thought on “Calculating without electricity

  1. Once you’re willing to accept approximations, you can do extremely well when calculating the number of trailing 0’s by dropping the floor functions and using all the terms of the infinite series, which leaves you with just n/4. For your example that gives an estimate of 2168827.25, compared to the exact value of 2168823.

    (Also, nice easter egg you put in there, Jenny! I didn’t notice it until I went to divide by 4.)

Leave a Reply

Your email address will not be published.