While working through a project euler problem I noticed an interesting pattern:

When writing down the numbers from $1$ to $n$ the total number of trailing zeros (called $S(n)$ for the rest of this post) is equal to $n - popcount(n)$ where $popcount(n)$ is the number of ones in the binary representation of $n$.

It took me a while to understand why this is true and even longer to formulate a somewhat elegant proof. What follows is my best try (so far).

## Example

1. 1
2. 10
3. 11
4. 100
5. 101
6. 110
7. 111
8. 1000
9. 1001
10. 1010

In the first $n = 10$ numbers there are $8$ trailing zeros. $popcount(n) = 2$, so the equation holds.

## Proof

A binary number has at least $z$ trailing zeros $\iff$ it is a multiple of $2^z$.

In the example above there are $\left\lfloor\frac{10}{2^1}\right\rfloor = 5$ numbers with at least one trailing zero, $\left\lfloor\frac{10}{2^2}\right\rfloor = 2$ numbers with at least two trailing zeros, and $\left\lfloor\frac{10}{2^3}\right\rfloor = 1$ numbers with at least three trailing zeros.

For arbitrary $n$ this can be written as

which is not really an infinite sum because after a while ($i > \log_2(n)$) all the remaining summands are zero.

$n$ can be written (binary notation) as $\sum\limits_{j = 0}^\infty a_j 2^j$ with $a_j \in \{0, 1\}$.

The division by $2^i$ can be understood as moving the “decimal” point in the binary representation of $n$ $i$ places to the left. $\left\lfloor x \right\rfloor$ is equivalent to cutting off everything after the “decimal” point of $x$ (independent of the base).

How does this apply to the equation from before? First I’ll introduce a simple indicator function that will make the next steps of the proof a little bit easier to follow:

What this allows us to do is to rewrite $\left\lfloor \ldots \right\rfloor$ by multiplying each $a_i 2^{j-i}$ with $I(j - i)$ so that it removed from the sum if $% $ (as part of the numbers behind the “decimal” point that are cut of).

If the step from $\sum\limits_{i=0}^{j-1} 2^i$ to $2^{j} - 1$ is not obvious, think about what happens if $1$ is added to a binary number that is made up entirely of ones: $1111_2 + 1_2 = 10000_2$.

## Applications

Because of the way binary multiplication works the number of trailing zeros in $n!$ is equal to $S(n)$, e.g. $10! = 3628800 = 1101110101111100000000_2$ has $S(10) = 10 - 2 = 0$ trailing zeros.

I’ll update this post once I find more practical applications for this.