Find the n-th base 2 palindrome

Question

So I want to compute the n-th base 2 palindrome, where n is a number less than or equal to 5000, and we can pick it.

So we know that in base 2 only odd numbers can be palindromes. Okay so that saves us some computation power, but still not enough.

My first thought was, to compute all the possible odd numbers in base 2 and check for every one of them if it is a palindrome. Then I would count in order how many palindromes there are, and when we reach the target $n$ we can print out the n-th palindrome. I think this is not enough, or my method of finding such numbers is bad. My question is, is there any other property of base 2 palindromes, besides that they are odd, that could help my search ? What kind of technique would you pick for search instead of a simple iteration (that's whagt I have done). (I am coding in python.)

Answer 1

For $n\ge 0$ there are $2^n$ palindromes of length $2(n+1)$, one for each possible choice of the second through $(n+1)$-st bits. For $n\ge 1$ there are also $2^n$ palindromes of length $2n+1$, again one for each possible choice of the second through $(n+1)$-st bits. Finally, there are $2$ palindromes of length $1$ (instead of just $1$). Thus, the total number of palindromes of length at most $2n$ is

$$\sum_{k=0}^{n-1}2^k+\sum_{k=0}^{n-1}2^k+1=2(2^n-1)+1=2^{n+1}-1\,.$$

The least $n$ such that the $k$-th palindrome has at most $2n$ bits is then the least $n$ such that $k\le 2^{n+1}-1$, i.e., $n=\lfloor\lg k\rfloor$. (In case you’ve not seen it before, $\lg$ is $\log_2$.) We can now determine the $k$-th palindrome as follows.

• Let $n=\lfloor\lg k\rfloor$, so that $2^n\le k<2^{n+1}$; the $k$-th palindrome must have $2n-1$ or $2n$ bits.

The $2^n$-th palindrome is the first palindrome with $2n-1$ bits, and there are $2^{n-1}$ palindromes of length $2n-1$, so the $(2^n+2^{n-1})$-st palindrome is the first one with $2n$ bits.

• Let $\ell=k-2^n$.
• If $\ell<2^{n-1}$, let $b_1b_2\ldots b_{n-1}$ be the $(n-1)$-bit binary representation of $\ell$; then the $k$-th palindrome is $1b_1b_2\ldots b_{n-2}b_{n-1}b_{n-2}\ldots b_2b_11$, of length $2n-1$.
• If $\ell\ge 2^{n-1}$, let $b_1b_2\ldots b_{n-1}$ be the $(n-1)$-bit binary representation of $\ell-2^{n-1}$; then the $k$-th palindrome is $1b_1\ldots b_{n-1}b_{n-1}\ldots b_11$, of length $2n$.

Examples: Suppose that we want the $11$-th palindrome; $\lg 11\approx 3.46$, so $n=3$, and $\ell=11-2^3=3<2^2$. The $2$-bit representation of $3$ is $11$, so the $11$-th palindrome is $11111$.

If instead we want the $13$-th palindrome, $n$ is still $3$, but $\ell=5\ge 2^2$. The $2$-bit representation of $\ell-2^2$ is $01$, so the $13$-th palindrome is $101101$.

Answer 2

Notice the following:

• 0 is a palindrome, 1 is a palindrome
• 11 is palindrome; so is 00, which is relevant to what follows but this is not a different number in base 2 than 0.
• 101 and 111 are the "unique" palidromes of length 3; but notice that they both wrap two 1s over the palindromes of length 1 (n - 2). 000 and 010 are the "non-unique palindromes", and 010 represents a number (10) which is not a palindrome when "left-trimmed".
• 1001 and 1111 are the unique palindrome, and wrap 1s over the palindromes of length n-2 (both unique and non-unique); 0000, 0110 are the non-unique (wrapping 0s around the same n-2 palindromes).

Etc, with this pattern (two arrays, one of "all" palindromes, one of "unique" palindromes; and wrapping 0s or 1s around previous palindromes of length n-2), you should have a simpler way to generate all palindromes. Then, when your "unique" palindrome array reaches the right size, just return the $n$-th element.

Answer 3

Yet another idea, use the fact that odd length palindromes need it's middle digit repeated an odd number of times total. Whereas, even length ones need all digits an even number of times. Also, half your search space: take the end two bits off, and bitxor with the Mersenne number($2^n-1$ aka base 2 repunit) of the length you were at, it's also a palindrome of length wanted.