3
$\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$
  • 1
    $\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$ – Robert Israel Nov 24 '15 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 '15 at 1:00
2
$\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$
3
$\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$
  • $\begingroup$ So how does the number of factors of 5 relate to the number of zeros? $\endgroup$ – m0meni Nov 24 '15 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$ – Ross Millikan Nov 24 '15 at 1:12
  • $\begingroup$ @RossMillikan That makes a lot of sense now thank you. $\endgroup$ – m0meni Nov 24 '15 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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