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?
[Math] How many numbers below 2048 are binary palindromes
binarycombinatoricspalindrome
Best Answer
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$)