**Problem Detail:**

Probability-related Info theory question that I can't figure out. Thanks in advance!

###### Asked By : AJQ

###### Answered By : orlp

I assume you are talking about the binary digits of all nonnegative integers < $2^{16}$.

The first binary digit of any positive integer must be $1$, because otherwise it's a leading zero and that means we're counting numbers twice. However, if we do not want two consecutive digits to be the same, this uniquely determines the rest of the bits, because they must alternate: $1010101...$.

So for $b > 1$, there exists exactly one $b$-bit integer with no consecutive binary digits.

For $b = 1$ there are two strings: $0$ and $1$.

Thus, if we are interested in the number of integers below $2^{16}$ without consecutive digits, there is one 16-bit number, one 15-bit, .. one 2-bit and two 1-bit numbers. So the answer is 17.

For completeness' sake, here they are:

`0 = 0 1 = 1 2 = 10 5 = 101 10 = 1010 21 = 10101 42 = 101010 85 = 1010101 170 = 10101010 341 = 101010101 682 = 1010101010 1365 = 10101010101 2730 = 101010101010 5461 = 1010101010101 10922 = 10101010101010 21845 = 101010101010101 43690 = 1010101010101010 `

Question Source : http://cs.stackexchange.com/questions/63705

**3200 people like this**