Showing posts from January 28, 2018

Trailing zeroes

A week or so ago someone mentioned the following problem:
How many trailing zeroes does 1000! have [when written out in base ten, of course]? Easy enough to find...

Prelude> length $ takeWhile (== '0') $ reverse (show (product [1..1000])) 

But is there a better way? Yes, there is. After reading that someone said he did it in his head, the way to do it in your head occurred to me. *slaps forehead*
1000!, like any positive integer, has a unique prime factorization. In particular, we're interested in the primes 5 and 2, because 10 is 5 * 2. They certainly both appear in the prime factorization of 1000!, and they thus have positive exponents in said factorization. Let m be the exponent for 5, and let n be the exponent for 2. How to calculate them? Let's start with five. There are 200 multiples of 5 between 1 and 1000.There are 40 multiples of 25 between 1 and 1000.There are 8 multiples of 125 between 1 and 1000.There's 1 multiple of 625 between 1 and 10…