Find the n-th base 2 palindrome

elementary-number-theorypalindrome

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.

  • 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$.

Related Question