Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is not homework, just asked out of curiosity. I wondered how many zeroes could be found at the end of $1990!$ . I computed something that seemed to work and found out 439. So I computed it in Python, and it returned 494 zeroes, so I'm 55 short.

My reasoning went like this : I get 2 zeroes by series of 10 consecutive numbers. The one that can be divided by 10 gives one zero, and I get another one from the multiplication of the one ending with 2 and the one ending with 5. So 199*2 = 398. But I also have 2 zeroes by hundreds, one comming from the one divisible by 100, and one from XX20 * XX50. 19*2 = 38 more. Then same for thousands. I only get 3 zero more, from 1000, 200*500 and 1200*1500.

$398 + 38 + 3 = 439$

So here is my question:

How can I compute function $t0(n)$ where $t0(n)$ returns the number of trailing $0$ in $n! = factorial(n)$ ?

(Assume $factorial(n)$ is written in base 10, but even better for any base !)

share|improve this question

closed as too localized by Pete L. Clark, Reid Barton, Scott Morrison Feb 24 '10 at 20:02

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

4  
This question is better for a site like: www.artofproblemsolving.com –  Gerald Edgar Feb 24 '10 at 15:15

1 Answer 1

up vote 4 down vote accepted

Take any integer $x$, and let $t,f$ represent the highest integers such that $2^t | x$ and $5^f | x$. Then the number of trailing zeros in the base 10 representation of $x$ is $z := \min\{t,f\}$. (One way to see this is to note it must be at least z since you have $(2*5)^z | x$, so you can write $x = 10^z * y$ where not both $2,5|y$, and so $y$ can't have any trailing zeros.)

Going back to factorials, $n!$ will always have $t > f$, so to count the zeros, you just have to count the fives. The expression you want is $$ f = \sum_{i=1}^\infty \lfloor n / 5^i\rfloor. $$ But maybe there's a cleaner form.

(for 1990! this gives 495, not 494 as you said. I checked this numerically as well, I guess you have a bug.)

share|improve this answer
    
Oh yes, of course. My reasoning did not take into account the powers of 5, so 25 will provide two zeroes in the end, 125 will give 3, etc. Thanks ! –  Ghi Om Feb 24 '10 at 13:19
4  
An alternative to that sum is 1/(p-1) times the number minus the sum of the digits of the number written in base p. 1990 in base 5 is 30430, whose digits sum to ten. So, the number of 0s at the end is (1990-10)/4. –  Douglas Zare Feb 24 '10 at 22:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.