How many numbers below 2048 are binary palindromes?

Question

I have the following Number Systems problem.

"Given the numbers from $2$ to $2047$ (inclusive) represented in binary, how many are palindromes? The leading digit can't be zero."

How would I go about solving this most efficiently?

Answer 1

If the leading bit can't be zero, then neither can the last bit. So you can represent an $11$-bit binary palindrome as follows:

$$1\ b_1\ b_2\ b_3\ b_4\ x\ b_4\ b_3\ b_2\ b_1\ 1$$

where $x$ can be either $0$ or $1$, and $b_1b_2b_3b_4$ is any $4$-bit number. It follows that there must be $32$ numbers of this form. A $10$-bit palindrome will follow the same pattern, but without the $x$ in the middle, so there are sixteen $10$-bit palindromes. Similarly, for $9$-bit and $8$-bit palindromes, there are $16$ and $8$ possibilities respectively.

So the total number of palindromes in the range $2-2027$ (i.e., with $2–11$ bits inclusive) must be $32+16+16+8+8+4+4+2+2+1$, which is $93$.

An even easier method:

It just occurred to be that there's another way of looking at this problem. If you ignore the requirement that the leading digit must be $1$, then the entire set of palindromes reduces to:

$$b_1\ b_2\ b_3\ b_4\ b_5\ x^\prime\ b_5\ b_4\ b_3\ b_2\ b_1$$

where $x^\prime$ can be $1$, $0$ or nothing. If there are any leading zeroes, these are matched by an equal number of trailing zeroes. If we suppose that all the palindromes are post-processed by stripping the leading and trailing zeroes (e.g., by converting $00011011000$ to $11011$), then we can obtain the same result by multiplying the number of permutations of $b_1b_2b_3b_4b_5$ ($31$, because we are still excluding $00000$) by the number of possible values of $x^\prime$ ($3$)

Answer 2

If you also wanted to include leading zeroes for palindromic strings, such as from all possible 11-bit numbers in the range of $(2^{11})-1$ (i.e. so that a valid binary palindrome is also 00111111100) then the formula is:

Let n be the length of the number x in base 2 (i.e. x exists in the range $(2^{n})-1)$ then:

• if n is odd, (i.e. range is $(2^{11})-1)$ then the number of x's within that range that are palindromic strings equals: $(n+1)/2 == (2^{6})-1$
• if n is even, (i.e. range is $(2^{12})-1)$ then the number of x's within that range that are palindromic strings equals: $(n)/2 == (2^{6})-1$

As can be seen above these adjacent ranges share the same number of palindromic binary strings, but only when the even one is the larger neighbor (i.e. $(2^{10})-1$ only has $(2^{5})-1$ palindromes, while $(2^{11})-1$ has $(2^{6})-1$.