How Many Zeros Hides 100!
The problem
The number ends in a long run of zeros. How many trailing zeros does it have — that is, what is the largest such that divides ?
- A trailing zero is produced by a factor .
- You are asked for the count, not for the value of .
Take a minute
Reveal hint 1
Every factor of needs one and one . Which of the two runs out first in ?
Reveal hint 2
Count factors of in three passes: multiples of , of , and of .
Solution
Answer trailing zeros.
Derivation
-
Decide which prime is the bottleneck.
-
Count multiples of .
-
Add the second factor from multiples of .
-
Add the third factor from .
-
Total.