Treebeard's Stumper Answer 28 January 2000

Stumper 100!

After 3 1/2 years of writing stumpers for the Dunn Middle School Friday Newsnote, this is stumper number 100! Yahoo! "100!" is also a math expression pronounced "100 factorial". It means the product of all the whole numbers up to that number multiplied together. For example, 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 = 3,628,800. Note the two zeros at the end. 100! is a huge number, way too big for my calculator. But I know it ends with an even longer string of zeros. How many zeros are there at the end of 100 factorial? How about 1000!? (Hint: 10 = 2 x 5)

One hundred factorial (100!) is a huge number of 158 digits, but I know it ends with 24 zeros. We add a zero to the tail of a number whenever we multiply by 10, which is 2 x 5. There are lots of twos as factors of 100!, but not as many fives, so the number of zeros will be the same as the number of fives. The factors 5, 10, 15, 20, ... each contribute a five, and 25, 50, 75, and 100 each add an extra. So the total is 100 / 5 + 100 / 25 = 24. Calculators are handy, but they're not always the best tool for thinking about numbers!

Notes:

The factorial function n! is a useful function for solving real-world problems involving combinations. How many ways can 3 people sit in 3 chairs? There's 3 choices for the first person, which leaves 2 choices for the second person, and the last person takes what's left, like this:

A B C	B A C	C A B
A C B	B C A	C B A

That's 3 x 2 x 1 = 3! = 6 combinations. By the same reasoning, there are

52! = 80658175170943878571660636856403766975289505440883277824000000000000

possible card shuffles. Factorials get big fast! And as they grow, they acquire ever-growing tails of zeros. There's a factorial [!] button on most calculators, but my TI-30 can only figure 11! before dropping digits in scientific notation. This number stumper needs a different strategy.

Graybear explains it like this:

If you factor all of the numbers between 1 and 100, inclusive, as follows:

1 x 2 x 3 x (2 x 2) x 5 x (2 x 3) x 7 x (2 x 2 x 2) x (3 x 3) x ...

and rearrange the primes, you will get:

100! = 2^97 x 3^48 x 5^24 x 7^16 x 11^9 x 13^7 x 17^5 x 19^5 x 23^4 x 29^3 x 31^3 x 37^2 x 41^2 x 43^2 x 47^2 x 53 x 59 x 61 x 67 x 71 x 73 x 79 x 83 x 89 x 97

A zero appears on the end for each (2 x 5) that is included. Since the power of 5 is 24 (and the power of 2 is >24), there are 24 zeros at the end of 100!.

It's easy to count the trailing zeros of 1000! with the same trick I used in my answer. Truncate each division to the lowest whole number and stop when the quotient is less than 1.

    1000   1000   1000    1000
    ---- + ---- + ----- + ------- = 200 + 40 + 8 + 1 = 249 trailing zeros
      5     5x5   5x5x5   5x5x5x5

In general, you can use this method to calculate the factors of any prime p in n!

Or as text:

           n
    Sum  [---]  for p^i <= n, and [x] is the largest integer <= x
          p^i

For example, there are this many factors of 2 in 100!

     100     100     100     100     100     100 
    [---] + [---] + [---] + [---] + [---] + [---] = 50 + 25 + 12 + 6 + 3 + 1 = 97
      2       4       8       16      32      64

Since the factorial of a number is a multiple of every whole number less than it, this provides an easy way to factor big factorials. Just use this procedure for every prime before it.

Big factorials can be approximated by Stirling's formula, named after the 18th century Scottish mathematician James Stirling. It's a startling formula that uses the two most-used transcendental numbers in a problem that doesn't have anything to do with either!

    n! ~= sqrt(2*pi*n) * (n/e)n

This is still too much for my calculator when n = 100, but by using natural logarithms (Log_e or Ln), you can at least count the digits in big factorials:

                Log(2n) + Log(pi)
                -----------------  + n (Log(n) - 1)
                        2
    digits ~=  -------------------------------------
                             Log(10)

When I manage to press the right buttons on my calculator for n = 100, I get 157.97 = 158 digits, which is right.

Graybear got a value for 100! with his calculator, and I've been wondering how he did it. He wrote:

My calculator gives 100! = 9.33262154439441 x 10^157. I also know it ends with a string of 24 zeros, so written out it will look like this:

100! = 93,326,215,443,944,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,
       XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,
       XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XXX,XX4,000,000,000,
       000,000,000,000,000

Maybe Graybear used Stirling's approximation to figure his answer, but my calculator can't figure that without overflow either. Then I realized there's an easy "lo-tech" way to get the answer. Just break up the product and then multiply the pieces. With patience, this would work for very large factorials.

1 x 2 x 3 x ... x 69 = 1.7112 x 10^98
70 x 71 x ...x 100 = 5.4538 x 10^59

Multiplying the decimals and adding the powers gives:

(1.7112 x 5.4538) x 10^(98 + 59) = 9.3326 x 10^157

Which is just right to 5 significant places.

Martin Gardiner quotes a letter from Robert E. Smith commenting that "using Stirling's formula for arriving at large factorials is analogous to a blind man trying to visualize an elephant by grasping a couple of inches of it's trunk in one hand and the tip of it's tail in the other." Big numbers have their mysteries!

Look close at Graybear's partial answer and notice that he correctly picked 4 as the last non-zero digit of 100 factorial. That happens to be right, but he now says it was a lucky guess. The complete series of last non-zero digits of n! for n = {0..100} is given in Sloane's A008904. There is no easy pattern in this:

0:	1,1,2,6,4,2,2,4,2,8,8,8,6,8,2,8,8,6,8,2,4,4,8,4,6,4,4,8,4,6,
30:	8,8,6,8,2,2,2,4,2,8,2,2,4,2,8,6,6,2,6,4,2,2,4,2,8,4,4,8,4,6,
60:	6,6,2,6,4,6,6,2,6,4,8,8,6,8,2,4,4,8,4,6,8,8,6,8,2,2,2,4,2,8,
90:	2,2,4,2,8,6,6,2,6,4,4

I wrote a little BASIC program that figures big factorials up to 10 million factorial in principle, but I've only run it to 10,000! so far. It takes about an hour to figure the 35,660 digits of 10,000 factorial. It's pretty fast since it does all the arithematic in base 10,000,000. Basically, this breaks up the big numbers into "bins" that can be represented by 32 bit long integers in my BASIC compiler. After each multiplication, any carry is moved to the next bin, just like ordinary multiplication. It uses the hard drive to store intermediate results, so there's no limit on size, but I don't like the way it thrashes my hard drive when working with big numbers.

My BIGFAC program figures 100! in no time at all. Here's the report:

Factorial(100) is:
93326215443944152681699238856266700490715968264381
62146859296389521759999322991560894146397615651828
62536979208272237582511852109168640000000000000000
00000000

158 digits in 0 seconds (02-01-2000).
There are 24 trailing zeros.
100! has 239 factors of 25 primes.

Prime factors of 100!
2^97 3^48 5^24 7^16 11^9 13^7 17^5 19^5 23^4 29^3 31^3
37^2 41^2 43^2 47^2 53 59 61 67 71 73 79 83 89 97

Note that the prime factor 5^24 gives the number of trailing digits. The report for 1000! and 10,000! is available as a separate text file. I think it's interesting how long sequences of random-looking digits are anything but random when you know what they really are!

Playing with my program, I noticed an interesting pattern in the numbers of trailing zeros:

10!	7 digits	2 trailing zeros
100!	158 digits	24 trailing zeros
1,000!	2,568 digits	249 trailing zeros
10,000!	35,660 digits	2,499 trailing zeros
100,000!	456,573 digits	24,999 trailing zeros
1,000,000!	5,565,709 digits	249,998 trailing zeros	<--- !
10,000,000!	65,657,059 digits	2,499,999 trailing zeros

What is that 8 doing in 1,000,000!? I double checked by hand, and I'm sure it's right. Perhaps it's part of a larger pattern?

Here are some some Web links for more research on huge factorials.

• Eric Weisstein's World of Mathematics has info on the factorial function. This useful math reference is finally available on the Web without restriction. It's great for browsing.

• Sloane's On-Line Encyclopedia of Integer Sequences is a remarkable search engine for number sequences. You can enter a few numbers and it will return a list of matches to explore. There are many sequences involving factorials, including the sequence of factorials (A000142), the number of trailing zeros (A027868), and the last non-zero digit (A008904).

• Martin Gardner has a chapter on "Factorial Oddities" in his book Mathematical Magic Show (Vintage, 1978). Unfortunately this collection of classic Scientific American Mathematical Games columns is currently not available from Amazon, but look at their Martin Gardner index page to see how many of his great books are available!

• I love playing with numbers, and good ol' DOS BASIC (actually PDS 7.1) is still my favorite tool! My small BIGFAC program is available with source and executable from Treebeard's Basic Vault. It's a fast program that finds factorials up to 10,000,000 factorial. BIGNUM (for DOS) and BNC (for Win3.1, but should work with Win98) are more ambitious big number programs. But they're slower, since they do everything digit-by-digit in base-10 (using strings) just like we do on paper. I prefer BIGNUM, but BNC can turn big numbers into MIDI sounds!

Back to Stumper

Last modified .