Trailing Zeros of a Factorial

• • Leave a reply

Math question: How many trailing zeros does 51! have?

The other day, I was studying up for job interviews and I ran across this problem. I haven't seen this before so I figured it's worth blogging.

In case you’re not familiar with the notation, 51! is pronounced 51 factorial. The factorial of a number is computed by multiplying together all the integers leading up to and including that number. For example, 4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24 and 6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720

As you can see, factorials grow quick which means 51! is a very large number and, because of this, computing its value is not as straight forward as it might seem. Many calculators do not have a factorial function and those that do probably round the result to something along the lines of 1.551119 \times 10^{66}. However, using a computer algebra system such as Mathematica, Wolfram Alpha or Maxima, we can compute it easily. Plugin in 51! into Maxima yields:

1,551,118,753,287,382,280,224,243,016,469,303,211,063,259,720,016,986,112,000,000,000,000

A quick count tells us there are 12 trailing zeros. Now, how do we mathematically compute the number of trailing zeros without expanding the factorial?

First off, let's expand 51! into its multiplicative form so we can see all its terms:

\begin{aligned} 51! = & 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15 \cdot 16 \cdot 17 \cdot 18 \cdot 19 \cdot 20 \cdot 21 \cdot 22 \cdot 23 \cdot 24 \cdot 25 \cdot 26 \cdot 27 \cdot \\ & 28 \cdot 29 \cdot 30 \cdot 31 \cdot 32 \cdot 33 \cdot 34 \cdot 35 \cdot 36 \cdot 37 \cdot 38 \cdot 39 \cdot 40 \cdot 41 \cdot 42 \cdot 43 \cdot 44 \cdot 45 \cdot 46 \cdot 47 \cdot 48 \cdot 49 \cdot 50 \cdot 51 \end{aligned}

It’s pretty obvious that multiplying any number times ten will yield a number will a trailing zero. The expanded factorial allows us to see that there are only 5 terms that have 10 as a factor: 10, 20, 30, 40, and 50. However, there are other ways to get 10. Looking through the terms, 2 \cdot 5 = 10 which brings us to six trailing zeros but that’s only half of them. Where are the rest hiding? Are there any more 2 \cdot 5? Yes!

If we take a close look at 15 \cdot 8 and breakdown each factor into its prime factorization, we get (3 \cdot 5)\times(2 \cdot 2 \cdot 2). As you can see, contained within the prime factorization, there is 2 \cdot 5 so 15 \cdot 8 will lead to another trailing zero. Now we need to find all the terms that have a 2 or a 5 as part of their prime factorization.

Finding all the terms that have a prime factor of five is easy. We just need to compute \frac{51}{5} which yields ten. This includes all the terms that are a multiple of 10 so we need to be careful we don’t count them twice. Now, do we have enough terms with a prime factor of 2 to pair with the 10 fives? Yes we do. Since every other term is even, we have at least \frac{51}{2} such terms. That’s so many we can neglect actually computing exactly how many and know there are enough.

Using this new technique, we are up to 10 trailing zeros but we must be missing something because we know there are twelve of them. Are there more 5's hiding? Yep. Some terms are more than one 5 as a prime factor. One of these is 25 which is 5 \cdot 5 or 5^2. One of the fives has already been accounted for so we only account for one more trailing zero. Where’s the last one? It’s in 50 because its prime factorization is 5 \cdot 5 \cdot 2 or 25 \cdot 2. That’s all 12 trailing zeros.

To summarize all the steps,

  1. Tally all the terms that have a factor of 5. Mathematically that's \frac{51}{5} = 10, ignoring the reminder.
  2. Find all the terms that have multiple 5’s a factors. These will always be the powers of 5 that are smaller than the number you are working with. For example, 5^2 = 25 which is less than 51 so we need to use it. On the other hand, 5^3 = 125 so we don’t need it. So, \frac{51}{25} = 2, ignoring the reminder.
  3. Add them up. Step 1 yielded 10 trailing zeros and step 2 yield 2 trailing zeros. And 10 + 2 = 12.

What if the number is larger, say 126!? Once expand, it becomes:

\begin{aligned}126! = & 23,721,732,428,800,468,856,771,473,051,394,170,805,702,085,973,808,045,\\ & 661,837,377,170,052,497,697,783,313,457,227,249,544,076,486,314,839,447,\\ & 086,187,187,275,319,400,401,837,013,955,325,179,315,652,376,928,996,065,\\ & 123,321,190,898,603,130,880,000,000,000,000,000,000,000,000,000,000 \end{aligned}

Again, a quick count tells us there are 31 trailing zeros. Applying the steps above:

Step 1: \frac{126}{5} = 25, again ignoring the remainder.
Step 2: \frac{126}{25} = 5 and since 126 is larger than 5^3 we also include \frac{126}{125} = 1.
Step 3: 25 + 5 + 1 = 31 trailing zeros.

One more example: 1382! (a really really big number that Maxima won't compute)
Step 1: \frac{1382}{5} = 276.
Step 2: \frac{1382}{25} = 55, \frac{1382}{125} = 11, and, now we need 5^4 = 625 as well, \frac{1382}{625} = 2.
Step 3: 276 + 55 + 11 + 2 = 344 trailing zeros.

In short, you need to find all the terms that produce 10, but not in the terms themselves, in the prime factorization of all the terms. Any term that has a 5 as part of its prime factorization will, along with a 2 possibly from factoring another term, yield a 10 and a trailing zero.

Leave a Reply