Enigma 1697

Spoiler for New Scientist Enigma 1697:

I have before me a number, which when written in binary is palindromic and has n digits. If I told you the value of n, and you wrote a list of all the possible palindromic binary numbers of length n, your list would have n numbers in it.

If your list was in ascending numeric order, and I told you the difference between my number and the next higher number in the list, you would be able to identify my number.

What is my number, in decimal form?

I found this one way easier than most Enigmas, though there’s an ambiguity. Are leading zeroes allowed? That is, is 0110 a palindromic binary number for purposes of this puzzle?

Probably not, but we can solve it either way.

If we allow leading zeroes, then there are 2m m-bit (I assume “digit” above means bit) binary numbers, which means there are 2m 2m-bit palindromic binary numbers (obtained by taking each m-bit number and concatenating it with its reversal) and 2m+1 (2m+1)-bit palindromic binary numbers (obtained by taking each m-bit number and concatenating it with either a 0 or a 1 and its reversal). So we’re looking for n = 2m such that 2m = 2m (obviously not 2m+1 = (2m+1)). That’s easy: n = 4. We can just write down the four palindromes — 0000, 0110, 1001, 1111 — then convert to decimal and find the differences or, what the heck, just find them in binary (binary subtraction, it’s good for your brain): 110, 11, and 110. The second difference is unique so the answer is 0110. In decimal, 6.

If we do not allow leading zeroes, then we throw out half the palindromic numbers (each one that begin and ends with 0 has a counterpart that begins and ends with 1, and vice versa) so there are 2m-1 2m-bit palindromic binary numbers and 2m (2m+1)-bit palindromic binary numbers. So we’re looking for n = 2m such that 2m-1 = 2m. This time n = 8. And again it’s easy to write down the palindromes — 10000001, 10011001, 10100101, 10111101, 11000011, 11011011, 11100111, and 11111111 — and get their binary differences — 11000,  1100, 11000, 110, 11000, 1100, 11000. The unique one is 110 so the answer is 10111101 binary or, in decimal, 189.