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.)
Best Answer
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.
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.
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$.