Trailing zeroes in binomial coefficient

Question

I have a doubt regarding trailing zeroes in binomial coefficients...

Question: How would you calculate the number of trailing zeroes in the binomial coefficient of ${n\choose r}$ upto values of $1000$? Is there any efficient method for doing so?

Answer 1

To find the number of trailing zeroes in ${n\choose r}$, we have to find the exponent of $10=(2\times 5)$ in the expression.
Since the exponent of $5$ will always be smaller than the exponent of $2$, we can just find the exponent of $5$ in it.
The exponent of any prime $p$ in $n!$ is given by this expression $$E_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots\infty$$ $$=\sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor$$ Since $${n\choose r}=\frac{n!}{r!(n-r)!}$$ We can define the exponent of $5$ in it as $$E_5(n!)-E_5(r!)-E_5((n-r)!)$$
The exponent of $5$ will simply be the exponent of $10$, and therefore the number of trailing zeroes. Even though it unnecessary, you can find the exponent of $2$ to confirm that it is, in fact, more than the exponent of $5$ in it.

Answer 2

I would just like to add to @AvZ 's answer that for binomial coefficients the exponent of $5$ can be larger than the exponent of $2$ in some cases (eg. for ${177\choose 113}$ $E_5=3$ but $E_2=1$)

Therefore, with the same symbols as before, $${n\choose r}=\frac{n!}{r!(n-r)!}$$ $$E_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots=\sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor$$

the formula to calculate the trailing zeroes of a binomal coefficient is: $$E_5=E_5(n!)-E_5(r!)-E_5((n-r)!) $$ $$E_2=E_2(n!)-E_2(r!)-E_2((n-r)!) $$ $$min(E_5, E_2)$$