Totem Pole sequences

Question

Worth a shot:

Find sequences of consecutive integers with consecutive bit counts.

I'm not very good at this sort of thing, so I managed 8,9.

Answer 1

For $n\in\Bbb N$ let $b(n)$ be the number of $1$ bits in the binary representation of $n$. If $n$ is even, $b(n+1)=b(n)+1$. Now suppose that $n$ is odd, and let $k$ be the number of consecutive $1$ bits at the low-order end of the binary representation of $n$; adding $1$ to $n$ switches all $k$ of those $1$ bits to $0$ and switches the $0$ bit immediately to their left to $1$, so its net effect is to subtract $k-1$ $1$ bits. Since $k-1\ge 0$, $b(n+1)\le b(n)$ when $n$ is odd. Thus, strings of length $2$ are the best you can get, and you get one of them for every even-odd pair of consecutive non-negative integers.