Explanation for the the number of trailing zeros in a factorial.

Question

I was doing a programming problem that asked that I find the number of trailing zeros for a factorial, and I came up with this:

function zeros (n) {
  let numZeros = 0, power = 5;
  while (power <= n) {
    numZeros += Math.floor(n / power);
    power *= 5;
  }
  return numZeros;
}

Basically through trial and error I found that the number of zeros in a given factorial was equal to:

$$\frac{n}{5} + \frac{n}{25} +...+\frac{n}{5^x}$$

While $5^x$ was less than or equal to n, and $\frac{n}{5^x}$ was rounded down to an integer value.

I'd like to be able to write some kind of proof for this, but I don't know where to get started. I've never written a proof before.

Answer 1

You add a zero every time that you multiply by $10$. Since the only prime factors of $10$ are $2$ and $5$, then clearly the trailing number of zeros in a number is the minimum of the two exponents in the prime factorization of that number.

To relate this to the formula you found, note that when computing a factorial, you will add a zero to the end every time that you multiply by a multiple of $5$—there's always an upaired factor of $2$ available to make $10$. When that multiple of $5$ is also a multiple of $25$, you’ll add an extra zero, three zeros when you hit a multiple of $5^3$, and so on.

Answer 2

About de Polignac's formula: You found yourself how many factors 5 the number n! has: The number of factors 5 is n/5 + n/25 + n/125...

If you take other prime numbers, then you get very similar results: The number of factors 2 is n/2 + n/4 + n/8 ..., then number of factors 103 is n/103 + n/103^2 + n/103^3 ... and so on.

$s_p(n)$ is the formula you found, for the prime number p. You found how often the factor 5 is there; to turn that into a number you calculate $5^{your formula}$. And then you do that for all the primes and multiply, and you get the formula for n! on that page.