How Many Zeros End 100!?

[00:00:00]100 factorial, multiply every whole number from 1 to 100 together.

[00:00:06]The question, how many zeros does that number end in?

[00:00:11]Just to let you feel how fast this grows, 100 * 99 is 9,900 * 98 is already over 970,000 * 97 over 94 million.

[00:00:25]That's just three of the multiplications and there are 96 more waiting.

[00:00:30]If you run it all the way to the end, that's 158 digits long. Not the value, the length.

[00:00:38]So, how do we figure this out? Well, first notice that a trailing zero is just a factor of 10.

[00:00:44]Every zero on the end of a number means one more clean factor of 10 inside it.

[00:00:50]Also, 10 is 2 * 5.

[00:00:54]So, the real question isn't about zeros at all. It's inside the product of 1 2 3 all the way multiplied to 100, how many complete 2 * 5 pairs are there?

[00:01:07]Now, we should think about where those factors come from.

[00:01:11]Every second number in the product denotes a two.

[00:01:16]And twos are everywhere.

[00:01:18]How about fives? Only every fifth number brings one.

[00:01:23]So, twos are never the shortage.

[00:01:26]Every five that shows up will always find a two to pair with.

[00:01:31]Which means that the number of pairs, the number of zeros, is just the number of fives.

[00:01:38]Count the fives and that gives you the entire problem.

[00:01:42]Here's the first pass, just the multiple of fives themselves. That's 5 10 15 all the way up to 100. One factor of five each, one small tool before we count them. In case you haven't seen it, the floor function denoted like this just means round down to a whole number.

[00:02:01]The floor of 4.6 would be four, the floor of 20 would be 20.

[00:02:06]It counts how many whole times does this fit?

[00:02:10]And the floor of 100 divided by five is 20 25s.

[00:02:16]Now, if that were the whole story, the answer would be 20, but it's not.

[00:02:21]Because four numbers in that list are holding out on us.

[00:02:26]25 is 5 * 5. It denotes two fives.

[00:02:32]And so does every multiple of 25, 25, 50, 75, and 100.

[00:02:37]Those four numbers each smuggle in a second five the first pass didn't count.

[00:02:43]The floor of 100 divided by 25 is four.

[00:02:47]And we should ask ourselves, do we have to keep going with this logic check? Do we need like a third pass here?

[00:02:54]Well, a third multiple of five would be 125, which is bigger than 100, bigger than the number we started with.

[00:03:03]So, our count stops. We had 20 from before, then four more after for 24. And that's it, exactly 24 zeros and 100!

[00:03:14]factorial.

[00:03:16]And what's pretty cool about this is this scales.

[00:03:20]This two-step move generalizes. If you keep dividing by powers of five until they outgrow the number, like on 1,000 factorial, we can count the number of ending zeros in the same way.

[00:03:34]And basically get that 1,000 factorial ends with 249 zeros.

[00:03:40]And even though these factorials deal with whole numbers, I thought it would be fun to take the derivative of a factorial, the derivative of a factorial function, which sounds illegal since factorials only live on the whole numbers, at least traditionally.

[00:03:57]But there's a way to do it and you can see it in this video. Click the video on screen to check it out.

[00:04:03]I'll see you in that one.