While working through a project euler problem I noticed an interesting pattern:
When writing down the numbers from to the total number of trailing zeros (called for the rest of this post) is equal to where is the number of ones in the binary representation of .
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
- 0001
- 001 0
- 0011
- 01 00
- 0101
- 011 0
- 0111
- 1 000
- 1001
- 101 0
In the first numbers there are trailing zeros. , so the equation holds.
Proof
A binary number has at least trailing zeros it is a multiple of .
In the example above there are numbers with at least one trailing zero, numbers with at least two trailing zeros, and numbers with at least three trailing zeros.
For arbitrary this can be written as
which is not really an infinite sum because after a while ( ) all the remaining summands are zero.
can be written (binary notation) as with .
The division by can be understood as moving the "decimal" point in the binary representation of places to the left. is equivalent to cutting off everything after the "decimal" point of (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 by multiplying each with 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 to is not obvious, think about what happens when is added to a binary number that is made up entirely of ones: .
Trailing Zeros of
Let be the number of trailing zeros when is written in binary.
(see Binary Trailing Zeros of Products ), so .
Example: has trailing zeros.