Lovefilm, yes or no?

[Peter Corlett]

On 14 Apr 2010, at 17:47, David Alban wrote:
> i would think that any factorial N! would end in zero if N > 9.  but i
> have no idea how many zeroes are at the end of <128!>.

Well, just give it a crack then. That's the point of the question, to see how people think. This one's particularly good because it's got several obvious answers, all of which are wrong, and it shows how hard people think.

The first thing to note is that multiples of ten have one zero, multiples of a hundred have two zeroes, and so on. So you are looking for all of the multiples of ten in the factorial.

The traps are not noticing that 2*5 = 10 - which you fell into - and that 10*10 = 100.

The general idea is to realise that a factorial is also the product of the prime factors of each number. That is:

N! = 1 * 2 * 3 * 4 * 5 * 6 ...
   = 1 * 2 * 3 * 2*2 * 5 * 2*3 ...
   = 2**a * 3**b * 5**c * 7**d ...

And then to realise that a >= b >= c >= d, and so you care about the value of c (as there will always be enough twos to multiply by all the fives you can find to make tens.) 

So, there are int(128/5) = 25 multiples of five, int(128/5**2) = 5 multiples of 25, and int(128/5**3) multiples of 125. So c = 25 + 5 + 1 = 31. So I reckon that 128! has 31 zeroes on the end.

Double-checking on a computer:

>>> reduce(lambda x, y: x * y, range(1,129)) % 10**31
0L
>>> reduce(lambda x, y: x * y, range(1,129)) % 10**32
80000000000000000000000000000000L

There is probably some neat trick with logarithms to calculate the number of zeros at the end of arbitrary N!, but I'm not a mathematician.