5
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ See de Polignac's formula. The number of trailing $0$'s in a number is the minimum of the exponents of $2$ and $5$ in its prime decomposition. $\endgroup$ Nov 24, 2015 at 0:54
  • $\begingroup$ @RobertIsrael I've having a tough time trying to relate de Polignac's formula to the one I came up with. Could you please help me see the connection in more detail? $\endgroup$
    – m0meni
    Nov 24, 2015 at 1:00

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ So how does the number of factors of 5 relate to the number of zeros? $\endgroup$
    – m0meni
    Nov 24, 2015 at 1:10
  • 3
    $\begingroup$ @AR7: If you factor the factorial into primes, each zero represents a factor of $2 \cdot 5$. As there are lots more factors of $2$ than $5$, the number of zeros is set by the number of factors of $5$. As a sum of a geometric series, the number of zeros at the end of $n!$ will be just a few less than $\frac n4$ $\endgroup$ Nov 24, 2015 at 1:12
  • $\begingroup$ @RossMillikan That makes a lot of sense now thank you. $\endgroup$
    – m0meni
    Nov 24, 2015 at 1:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .