Palindromic numbers whose squares are palindromic too

Question

In any base $b>2$, there are infinite palindromic numbers whose squares are palindromic too: for any $n\geq 0$, if $a_n:=1\underbrace{0\dots 0}_{\text{n}}1_b$ then $a_n^2=1\underbrace{0\dots 0}_{\text{n}}2\underbrace{0\dots 0}_{\text{n}}1_b$. Is this property true also in base $2$?

Answer 1

There are only finitely many base-$2$ palindromes whose square is also a base-$2$ palindrome. Namely, the trivial $0$ (if one counts that as a palindrome), $1$, and the not-quite-trivial $3 = 11_2$.

To see that, let's first look at numbers with few bits set. There's only one number with no bits set, $0$. Whether that should count as a palindrome is left to the reader. There's only one base-$2$ palindrome with exactly one bit set, namely $1$. For base-$2$ palindromes with exactly two bits set, we easily see that $3$ is the only one whose square is also a base-$2$ palindrome. For if $x = 2^k + 1$ with $k \geqslant 2$, then $x^2 = 2^{2k} + 2^{k+1} + 1$, and there are only $k-2$ zeros between the first two ones, and $k$ zeros between the last two ones, hence $x^2$ is not a base-$2$ palindrome. Base-$2$ palindromes with exactly three bits set are of the form $x = 2^{2k} + 2^k + 1$, and then $x^2 = 2^{4k} + 2^{3k+1} + 2^{2k+1} + 2^{2k} + 2^{k+1} + 1$. For $k \geqslant 2$, we have $4k > 3k+1 > 2k+1 > 2k > k+1 > 0$, and we again have only $k-2$ zeros between the first two ones, and $k$ zeros between the last two ones in the binary representation of $x^2$. For $k = 1$ we have $x = 7$ and $x^2 = 49 = 110001_2$ which also isn't a base-$2$ palindrome.

So let's finally look at base-$2$ palindromes with at least four bits set. These are of the form $x = 2^k + 2^{k-a} + \dotsc + 2^a + 1$ with $1 \leqslant a < \frac{k}{2}$. Writing $x = 1 + 2^a\cdot u$ with $u$ odd, we see that $x^2 = 1 + 2^{a+1} u + 2^{2a}u^2$, so there are at least $a$ zeros between the last two ones in the binary representation of $x^2$ (exactly $a$ if $a \geqslant 2$, at least $2$ if $a = 1$). At the front, writing $x = 2^k + v$, with $2^{k-a} < v < 2^{k+1-a}$, we see that $x^2 = 2^{2k} + 2^{k+1}v + v^2$, and

$$2^{2k+1-a} < 2^{k+1}v + v^2 < 2^{2k+2-a} + 2^{2k+2-2a}, \tag{$\ast$}$$

so there are at most $a-2$ zeros between the first two ones in the binary representation of $x^2$ and hence $x^2$ is not a base-$2$ palindrome, unless we have carry at the front, i.e. $2^{k+1}v + v^2 \geqslant 2^{2k}$.

From $(\ast)$ it is readily seen that there is no carry at the front if $a \geqslant 3$, so we only need to look at the cases $a = 2$ and $a = 1$.

For $a = 2$, we have $x \equiv 5 \pmod{8}$ and therefore $x^2 \equiv 9 \pmod{16}$, so $x^2$ can only be a base-$2$ palindrome if $2^{2k+1} + 2^{2k-2} \leqslant x^2 < 2^{2k+1} + 2^{2k-1}$. But we have $x < 2^k + 2^{k-1}$ and hence

$$x^2 < (2^k + 2^{k-1})^2 = 2^{2k+1} + 2^{2k-2},$$

thus $x^2$ is never a base-$2$ palindrome when $a = 2$.

Last, we look at the case $a = 1$. If $x \equiv 7 \pmod{8}$, then $x^2 \equiv 1 \pmod{16}$, so there are at least three zeros between the last two ones in the binary representation of $x^2$, but then, since $x$ is a base-$2$ palindrome we have $2^k + 2^{k-1} + 2^{k-2} = 2^{k+1} - 2^{k-2} < x < 2^{k+1}$ and

$$(2^{k+1} - 2^{k-2})^2 = 2^{2k+2} - 2^{2k} + 2^{2k-4} = 2^{2k+1} + 2^{2k} + 2^{2k-4} < x^2 < 2^{2k+2},$$

so the binary representation of $x^2$ starts with two consecutive ones, and therefore $x^2$ is not a base-$2$ palindrome.

Thus we must have $x \equiv 3 \pmod{8}$ and consequently $x^2 \equiv 9 \pmod{16}$, so there are exactly two zeros between the last two ones in the binary representation of $x^2$, whence $x^2$ can only be a base-$2$ palindrome if $2^{2k+1} + 2^{2k-2} < x^2 < 2^{2k+1} + 2^{2k-1}$. This implies $x < 2^{k} + 2^{k-1} + 2^{k-3}$, so the binary representation of $x$ must be $1100\dotsc0011$ (leaving out the verification that $x = 51 = 110011_2$ and $x = 99 = 1100011_2$ don't have base-$2$ palindromic squares). But then $x \equiv 3 \pmod{16}$ and $x^2 \equiv 9 \pmod{32}$, so the binary expansion of $x^2$ ends with $01001$ and we must have $2^{2k+1} + 2^{2k-2} < x^2 < 2^{2k+1} + 2^{2k-2} + 2^{2k-3}$, which in turn implies $x < 2^k + 2^{k-1} + 2^{k-4}$, and thus, since $x$ shall be a base-$2$ palindrome, $x \equiv 3 \pmod{32}$. Now it is easily verified that for $x = 2^k + 2^{k-1} + 2 + 1$, the square is never a base-$2$ palindrome, and thus the last family of candidates is of the form

$$x = 2^k + 2^{k-1} + 2^{k-b} + \dotsc + 2^b + 2 + 1$$

with $b \geqslant 5$ (or in case $k = 2b$ of the form $2^{2b} + 2^{2b-1} + 2^b + 2 + 1$; the form is slightly different, the argument is the same). Writing $x = 1 + 2 + 2^b\cdot u$ with odd $u$, we find that

$$x^2 = 1 + 2^3 + 2^{b+1} + \dotsc,$$

so there are exactly $b-3$ zeros between the third-to-last and the penultimate one in the binary representation of $x^2$. On the other hand, from $2^k + 2^{k-1} + 2^{k-b} < x < 2^k + 2^{k-1} + 2^{k+1-b}$ we obtain

$$2^{2k+1} + 2^{2k-2} + 2^{2k+1-b} + 2^{2k-b} + 2^{2k-2b} < x^2 < 2^{2k+1} + 2^{2k-2} + 2^{2k+2-b} + 2^{2k+1-b} + 2^{2k+2-2b},$$

so there are at most $(2k-2) - (2k+1-b) - 1 = b-4$ zeros between the second and third one in the binary representation of $x^2$, which shows that $x^2$ isn't a base-$2$ palindrome for such $x$.