Table of Contents
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.