How does one easily calculate ?
Here denotes the “population count” or “sideways sum”, which is the number of 1s in the binary representation of (A000120).
which makes it possible to write the series as
After reversing the order of summation (which requires justification), he asks: For fixed , which values of has ? Note here that has the th bit set if and only if has the zeroth bit set. And a number has the zeroth bit set if and only if that number is odd. So if and only if for some . This means
for some . This provides us with the intervals of that we are interested in, so we have