Trailing zero

The number of trailing zeros in the decimal representation of n!, the factorial of a non-negative integer n, is simply the multiplicity of the prime factor 5 in n!. This can be determined with this special case of de Polignac's formula: :f(n) = \sum_{i=1}^k \left \lfloor \frac{n}{5^i} \right \rfloor = \left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + \left \lfloor \frac{n}{5^3} \right \rfloor + \cdots + \left \lfloor \frac{n}{5^k} \right \rfloor, \, where k must be chosen such that :5^{k+1} > n,\, more precisely :5^{k} \le n :k = \left \lfloor \log_{5} n \right \rfloor, and \lfloor a \rfloor denotes the floor function applied to a. For n = 0, 1, 2, ... this is :0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, ... . For example, 53 > 32, and therefore 32! = 263130836933693530167218012160000000 ends in :\left \lfloor \frac{32}{5} \right \rfloor + \left \lfloor \frac{32}{5^2} \right \rfloor = 6 + 1 = 7\, zeros. If n !, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero. Defining :q_i = \left \lfloor \frac{n}{5^i} \right \rfloor,\, the following recurrence relation holds: :\begin{align}q_0\,\,\,\,\, & = \,\,\,n,\quad \\ q_{i+1} & = \left \lfloor \frac{q_i}{5} \right \rfloor.\,\end{align} This can be used to simplify the computation of the terms of the summation, which can be stopped as soon as q i reaches zero. The condition is equivalent to == See also ==