4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Have you found even one such value of $x>1$ such that both $x$ and $x^2$ are palindromic in base $2$? $\endgroup$ – barak manos Aug 28 '16 at 9:00
  • 1
    $\begingroup$ @barak manos Yes. Take $3=11_2$ then $3^2=1001_2$. $\endgroup$ – Robert Z Aug 28 '16 at 9:08
  • $\begingroup$ OK, anything else besides that? $\endgroup$ – barak manos Aug 28 '16 at 9:12
  • 1
    $\begingroup$ @barak manos Yes, take $4523^2$ $\endgroup$ – Robert Z Aug 28 '16 at 9:37
  • 1
    $\begingroup$ The next values are $11991^2$, $18197^2$ and $141683^2$... $\endgroup$ – barak manos Aug 28 '16 at 9:40
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.