The number of digits in n! (Part 4)

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation for the number of digits in $n!$ . And I never could figure it out. However, even though I was not able to figure this out for myself, there is a very good approximation using Stirling’s approximation. The next integer after $\log_{10} n!$ gives the number of digits in $n!$ , and

$\log_{10} n! \approx \displaystyle \frac{\left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi)}{\ln 10}$

The graph below shows just how accurate this approximation really is. The solid curve is the approximation; the dots are the values of $\log_{10} n!$ . Not bad at all… the error in the curve is smaller than the size of the dots.

The following output from a calculator shows just how close the approximation to $log_{10} 69!$ is to the real answer. There are also additional terms to Stirling’s series that would get even closer answers.

As I mentioned earlier in this series, I’m still mildly annoyed with my adolescent self that I wasn’t able to figure this out for myself… especially given the months that I spent staring at this problem trying to figure out the answer.

First, I’m annoyed that I didn’t think to investigate $\log_{10} n!$ . I had ample experience using log tables (after all, this was the 1980s, before scientific calculators were in the mainstream) and I should have known this.

Second, I’m annoyed that I didn’t have at the tips of my fingers the change of base formula

$\log_{10} n! = \displaystyle \frac{\ln n!}{\ln 10}$

Third, I’m annoyed that, even though I knew calculus pretty well, I wasn’t able to get at least the first couple of terms of Stirling’s series on my own even though the derivation was entirely in my grasp. To begin,

$\ln n! = \ln (1 \cdot 2 \cdot 3 \dots \cdot n) = \ln 1 + \ln 2 + \ln 3 + \dots + \ln n$

For example, if $n = 10$ , then $\ln 10!$ would be the areas of the 9 rectangles shown below (since $\ln 1 = 0$):

The areas of these nine rectangles is closely approximated by the area under the curve $y = \ln x$ between $x =1\frac{1}{2}$ and $x = 10\frac{1}{2}$ . (Indeed, I chose a Riemann sum with midpoints so that the approximation between the Riemann sum and the integral would be very close.)

In general, for $n!$ instead of $10!$ , we have

$\ln n! \approx \displaystyle \int_{3/2}^{n+1/2} \ln x \, dx$

This is a standard integral that can be obtained via integration by parts:

$\ln n! \approx \bigg[ \displaystyle x \ln x - x \bigg]_{3/2}^{n+1/2}$

$\ln n! \approx \left[ \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - \left(n + \displaystyle \frac{1}{2} \right) \right] - \left[ \displaystyle \frac{3}{2} \ln \frac{3}{2} - \frac{3}{2} \right]$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

We can see that this is already taking the form of Stirling’s approximation, given above. Indeed, this is surprisingly close. Let’s use the Taylor approximation $\ln(1+x) \approx x$ for $x \approx 0$ :

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n \left[1 + \displaystyle \frac{1}{2n}\right] \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \ln \left(1 + \displaystyle \frac{1}{2n} \right) \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \displaystyle \frac{1}{2n} \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n + \left(n + \displaystyle \frac{1}{2} \right) \displaystyle \frac{1}{2n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n +\displaystyle \frac{1}{2} + \frac{1}{4n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \left(\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \right) + \displaystyle \frac{1}{4n}$

By way of comparison, the first few terms of the Stirling series for $\ln n!$ are

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi) + \displaystyle \frac{1}{12n}$

We see that the above argument, starting with an elementary Riemann sum, provides the first two significant terms in this series. Also, while the third term is incorrect, it’s closer to the correct third term that we have any right to expect:

$\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \approx 0.8918\dots$

$\displaystyle \frac{1}{2} \ln (2\pi) \approx 0.9189\dots$

The correct third term of $\displaystyle \frac{1}{2} \ln(2\pi)$ can also be found using elementary calculus, though the argument is much more sophisticated that the one above. See the MathWorld website for details.

The number of digits in n! (Part 3)

The following graph shows the number of digits in $n!$ as a function of $n$ .

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation that would fit these points. And I never could figure it out.

When I took calculus in college, I distinctly remember getting up the nerve to ask my professor, the great L.Craig Evans (now at UC Berkeley), if he knew how to solve this problem. To my great consternation, he immediately wrote down what I now realize to be the right answer, using Stirling’s approximation:

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \frac{1}{2} \ln (2\pi)$

While I now know that this was the way to go about solving this problem, I didn’t appreciate how this formula could help me at the time. I only saw the $n!$ on the left-hand side and did not see the immediate connection between this formula and the number of digits in $n!$ .

But now I know better.

For starters, the number of base-10 digits in a number $n$ is always the next integer greater that $\log_{10} n$ . For example, $\log_{10} 2000 \approx 3.301$, and the next integer larger than $3.301$ is 4. Unsurprisingly, the number $2000$ has 4 digits.

Second, the change of base formula for logarithms gives

$\log_{10} n! = \displaystyle \frac{\ln n!}{\ln 10}$

Therefore, the number of digits in $n!$ will be about

$\displaystyle \frac{\left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \frac{1}{2} \ln (2\pi)}{\ln 10}$

The graph below shows just how accurate this approximation really is. The solid curve is the approximation; the dots are the values of $\log_{10} n!$ . (In other words, this series of dots are only slightly different than the dots above, which have integers as coordinates.) Not bad at all… the error in the approximation is smaller than the size of the dots in this picture.

The number of digits in n! (Part 2)

The following graph shows the number of digits in $n!$ as a function of $n$ .

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation that would fit these points. And I never could figure it out.

In retrospect, my biggest mistake was thinking that the formula had to be something like $y = a x^m$ , where the exponent $m$ was a little larger than 1. After all, the graph is clearly not a straight line, but it’s also not as curved as a parabola.

What I didn’t know then, but know now, is that there’s a really easy way to determine to determine if a data set exhibits power-law behavior. If $y = a x^m$ , then

$\ln y = \ln a + m \ln x$ .

If we make the substitutions $Y = \ln Y$ , $B = \ln a$ , and $X = \ln x$ , then this equation becomes

$Y = m X + B$

In other words, if the data exhibits power-law behavior, then the log-transformed data would look very much like a straight line. Well, here’s the graph of $(X,Y)$ after applying the transformation:

Ignoring the first couple of pots, the dots show an ever-so-slight concave down pattern, but not enough that would have discouraged me from blindly trying a pattern like $y = a x^m$ . However, because these points do not lie on a straight line and exhibit heteroscedastic behavior, my adolescent self was doomed to failure.

The number of digits in n! (Part 1)

When I was in school, perhaps my favorite pet project was trying to find a formula for the number of digits in $n!$ . For starters:

$0! = 1$ : 1 digit
$1! = 1$ : 1 digit
$2! = 2$ : 1 digit
$3! = 6$ : 1 digit
$4! = 24$ : 2 digits
$5! = 120$ : 3 digits
$6! =720$ : 3 digits
$7! = 5040$ : 4 digits
$8! = 40,320$ : 5 digits

I owned what was then a top-of-the-line scientific calculator (with approximately the same computational capability as a modern TI-30), and I distinctly remember making a graph like the following on graph paper. The above calculations contribute the points $(0,1)$ , $(1,1)$ , $(2,1)$ , $(3,1)$ , $(4,2)$ , $(5,3)$ , $(6,3)$ , $(7,4)$ , and $(8,5)$ .

I had to stop (or, more accurately, I thought I had to stop) at $69!$ because my calculator couldn’t handle numbers larger than $10^{100}$ .

I stared at this graph for weeks, if not months, trying to figure out an equation that would fit these points. And I never could figure it out.

And, to this day, I’m somewhat annoyed at my adolescent self that I wasn’t able to figure out this puzzle for myself… since I had all the tools in my possession needed to solve the puzzle, though I didn’t know how to use the tools.

In this series of posts, I’ll answer this question with the clever application of some concepts from calculus and precalculus.

Compound Interest and Mary Poppins

What would have happened if Michael Banks had invested his tuppence in a savings account? FiveThirtyEight has the answer.

Calculators and Complex Numbers: Index

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on how the trigonometric form of complex numbers, DeMoivre’s Theorem, and extending the definitions of exponentiation and logarithm to complex numbers.

Part 1: Introduction: using a calculator to find surprising answers for $\ln(-5)$ and $\sqrt[3]{-8}$ . See the video below.

Part 2: The trigonometric form of complex numbers.

Part 3: Proving the theorem

$\left[ r_1 (\cos \theta_1 + i \sin \theta_1) \right] \cdot \left[ r_2 (\cos \theta_2 + i \sin \theta_2) \right] = r_1 r_2 (\cos [\theta_1+\theta_2] + i \sin [\theta_1+\theta_2])$

Part 4: Proving the theorem

$\displaystyle \frac{ r_1 (\cos \theta_1 + i \sin \theta_1) }{ r_2 (\cos \theta_2 + i \sin \theta_2) } = \displaystyle \frac{r_1}{r_2} (\cos [\theta_1-\theta_2] + i \sin [\theta_1-\theta_2])$

Part 5: Application: numerical example of De Moivre’s Theorem.

Part 6: Proof of De Moivre’s Theorem for nonnegative exponents.

Part 7: Proof of De Moivre’s Theorem for negative exponents.

Part 8: Finding the three cube roots of -27 without De Moivre’s Theorem.

Part 9: Finding the three cube roots of -27 with De Moivre’s Theorem.

Part 10: Pedagogical thoughts on De Moivre’s Theorem.

Part 11: Defining $z^q$ for rational numbers $q$ .

Part 12: The Laws of Exponents for complex bases but rational exponents.

Part 13: Defining $e^z$ for complex numbers $z$

Part 14: Informal justification of the formula $e^z e^w = e^{z+w}$ .

Part 15: Simplification of $e^{i \theta}$ .

Part 16: Remembering DeMoivre’s Theorem using the notation $e^{i \theta}$ .

Part 17: Formal proof of the formula $e^z e^w = e^{z+w}$ .

Part 18: Practical computation of $e^z$ for complex $z$ .

Part 19: Solving equations of the form $e^z = w$ , where $z$ and $w$ may be complex.

Part 20: Defining $\log z$ for complex $z$ .

Part 21: The Laws of Logarithms for complex numbers.

Part 22: Defining $z^w$ for complex $z$ and $w$ .

Part 23: The Laws of Exponents for complex bases and exponents.

Part 24: The Laws of Exponents for complex bases and exponents.

Fun lecture on geometric series: Index

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series concerning one of my favorite lectures concerning various applications of geometric series.

Part 1: Introduction to generating functions.

Part 2: Enumeration problems; or counting how many ways $2.00 can be formed using pennies, nickels, dimes, and quarters. (The answer is 1463.)

Part 3: The generating function for the Fibonacci sequence.

Part 4: Using a generating function to find a closed-form expression for the (ahem) Quintanilla sequence, a close but somewhat less famous relative of the Fibonacci sequence.

Part 5: Reproving the formula for the Quintanilla sequence using mathematical induction.

Square roots and Logarithms Without a Calculator: Index

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on computing square roots and logarithms without a calculator.

Part 1: Method #1: Trial and error.

Part 2: Method #2: An algorithm comparable to long division.

Part 3: Method #3: Introduction to logarithmic tables. At the time of this writing, this is the most viewed page on my blog.

Part 4: Finding antilogarithms with a table.

Part 5: Pedagogical and historical thoughts on log tables.

Part 6: Computation of square roots using a log table.

Part 7: Method #4: Slide rules

Part 8: Method #5: By hand, using a couple of known logarithms base 10, the change of base formula, and the Taylor approximation $ln(1+x) \approx x$ .

Part 9: An in-class activity for getting students comfortable with logarithms when seen for the first time.

Part 10: Method #6: Mentally… anecdotes from Nobel Prize-winning physicist Richard P. Feynman and me.

Part 11: Method #7: Newton’s Method.

Why does 0! = 1? (Index)

Part 1: Multiplication and division.

Part 2: Combinatorics.

Mathematical Christmas gifts

Now that Christmas is over, I can safely share the Christmas gifts that I gave to my family this year thanks to Nausicaa Distribution (https://www.etsy.com/shop/NausicaaDistribution):

Euler’s equation pencil pouch: