1
$\begingroup$

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 !)

$\endgroup$
1
  • 4
    $\begingroup$ This question is better for a site like: www.artofproblemsolving.com $\endgroup$ Feb 24, 2010 at 15:15

1 Answer 1

4
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ 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 ! $\endgroup$
    – glmxndr
    Feb 24, 2010 at 13:19
  • 4
    $\begingroup$ 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. $\endgroup$ Feb 24, 2010 at 22:47

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