It is well-known that the number of trailing zeros in the factorial $k!$ is given by the nice function $$ z(k) := \sum\_{i \ge 1} \left\lfloor \frac{k}{5^i} \right\rfloor. $$


Now assume that we want to count how many nonnegative integers up to $n$ have an even number of trailing zeros in their factorial. We could just compute $z(k) \pmod 2$ for $k=0,1,2,\ldots,n$, but this is too slow for large $n$ (say, $n=10^{18}$). 


*Can we count those integers more efficiently? For example, in time polynomial in $\log n$?*


About the problem: This problem was described in a programming competition ([Problem F here](http://swerc.dsic.upv.es/ProblemSet2013/statements.pdf "SWERC 2013")). The [official solutions](http://swerc.dsic.upv.es/ProblemSet2013/solutions.pdf) describe an efficient algorithm (polynomial in the number of digits of $n$), based on visual inspection of the parity patterns. But there is no proof that the algorithm is correct. 
So an alternative question would be, why is that algorithm correct? 



Integers up to n having an even number of trailing zeros in their factorial
You can use a very similar reasoning to the one commonly used to prove [Lucas's lemma](http://en.wikipedia.org/wiki/Lucas%27_theorem). The method below is not very short, but I think it's transparent, and it's straightforward to adapt it to trailing zeros in any base $b$ congruent to any remainder 
$r$ mod $m$ (10, 0, 2 respectively in our case). You can probably also use it to prove the patterns that the solution you linked exploits.


To get some symmetry, let's define
$$F(n) = \#\left\{ 1 \le j \le n : 2 \mid z(k) \right\} - 
\#\left\{ 1 \le j \le n : 2 \nmid z(k) \right\}.$$
The number of even $z$'s up to $n$ can easily be recovered as $\frac{F(n)+n}2$.


Let ${\rm ord}\_p(n) = \max \{ t \in \mathbb Z : p^t | n\}$ denote the largest exponent of $p$ that divides $n \in \mathbb N$. Then, an alternative formula for $z$ is:
$$z(n) = \sum\_{i=1}^n {{\rm ord}\_5(i)},$$
the advantage being that the sequence $({\rm ord}\_5(i): i\in \mathbb N)$ is almost periodic in a sense: $({\rm ord}\_5(i): 1\le i \le 5^{k+1})$ is the same as $({\rm ord}\_5(i): 1\le i \le 5^k)$ five times, except for the last term.


Let's first compute $z(5^k)$ and $F(5^k)$ inductively (actually, we only care about $z$ mod $2$).


$$z(5^{k+1}) = 5\cdot z(5^k) + 1$$
$$F(5^{k+1}) = \left( 3+2\cdot(-1)^{z(5^k)} \right)\cdot F(5^k) + 2\cdot(-1)^{z(5^{k+1})}$$


Similarly, for $1 \le d < 5$:


$$z(d\cdot 5^k) = d\cdot z(5^k)$$
$$F(d\cdot 5^k) = \left( \left \lceil{\frac d 2}\right \rceil
+ \left \lfloor{\frac d 2}\right \rfloor \cdot(-1)^{z(5^k)} \right) \cdot F(5^k)$$


Finally, note that if $0 < b < 5^k$ and $5^k | a$, then
$$ z(a+b) = z(a) + z(b) $$
$$ F(a+b) = F(a) + F(b)\cdot(-1)^{z(a)} $$


If your number in base 5 is $n = \overline{ d\_{k-1}d\_{k-2}\dots d\_0 } \_{(5)}$, then this allows you to iteratively compute $F\left(\overline{ d\_{k-1}d\_{k-2}\dots d\_{k-j}00\dots0 } \_{(5)} \right)$ for $1 \le j \le k$, all in $O(k) = O(\log n)$ steps. (That is, if you assume that $F(j)$ will fit in a constant precision integer. As $F(i) = O(i)$, I think the real asymptotic runtime is $O(\log^2 n)$ for truly large values of $n$).


