A036236 and A078457

[Hans Havermann]

Theorem. There is no palindromic-in-binary positive integer x, except
x=1 and x=3, such that x^2 is also palindromic-in-binary.

Proof.

Assume that such integer x>3 exist.

Excluding some small trivially verifiable cases, the binary
representation of x must have one of the following three forms:
i) 100...001
ii) 101...101
iii) 11...11

Below we will show that neither of these cases delivers a required integer x.

i) Suppose that x = 100...001

We will show that x cannot be finite in this case - namely, if the
binary representation of x starts with 2^k (i.e., with one followed by
k zeros) for some k>=2, then it must start with 2^(k+2). This implies
that no required x exists.

Let n be the number of binary digits in x. Since the binary
representation of x starts with 2^k, we have
2^k * 2^(n-k-1) < x < (2^k + 1) * 2^(n-k-1)
and
2^(2k) * 2^(2n-2k-2) < x^2 < (2^(2k)+2^(k+1)+1) * 2^(2n-2k-2) <
2^(2k+1) * 2^(2n-2k-2),
implying that the number of binary digits in x^2 is 2n-1.

On the other hand, since x == 1 (mod 2^(k+1)), we have x^2 == 1 (mod
2^(k+2)), implying that x^2 starts with 2^(k+1). Hence,
2^(k+1) * 2^(2n-k-3) < x^2 < (2^(k+1)+1) * 2^(2n-k-3)
or
2^(2n-2) < x^2 < 2^(2n-2) + 2^(2n-k-3),
implying that
2^(n-1) < x < 2^(n-1) + 2^(n-k-3) = (2^(k+2) + 1) * 2^(n-k-3),
implying that the binary representation of x starts with 2^(k+2). Q.E.D.


ii) Suppose that x = 101...101.

Let n be the number of binary digits in x. Since the binary
representation of x starts with 5, we have
5 * 2^(n-3) < x < 6 * 2^(n-3)
and thus
(X)   25 * 2^(2n-6) < x^2 < 36 * 2^(2n-6).

Let m be the number of binary digits in x^2. Clearly, we have either
m=2n-1 or m=2n.

Since x == 5 (mod 8), we have x^2 == 25 == 9 (mod 16), implying that
x^2 starts with 9 (note that 9 = "1001" in binary is a palindrome
itself). Hence,
9 * 2^(m-5) < x^2 < 10 * 2^(m-5).
Depending on the value of m, we have either
9 * 2^(2n-6) < x^2 < 10 * 2^(2n-6), if m = 2n-1,
or
18 * 2^(2n-6) < x^2 < 20 * 2^(2n-6), if m = 2n.
Both these cases contradict to the inequality (X) above. Therefore, no
x of the form 101...101 exists. Q.E.D.


iii) Suppose that x = 11...11.

Similarly to the case i), we will show that x cannot be finite in this
case - namely, if the binary representation of x starts with 3*2^k
(i.e., with "11" followed by k zeros) for some k>=0, then it must
start with 3*2^(k+1). This implies that no required x exists.

Assume that k>0. The case k=0 can be considered similarly.

Let n be the number of binary digits in x. Since the binary
representation of x starts with 3*2^k, we have
3 * 2^k * 2^(n-k-2) < x < (3 * 2^k + 1) * 2^(n-k-2)
and
9 * 2^(2k) * 2^(2n-2k-4) < x^2 < (9 * 2^(2k) + 3 * 2^(k+1) + 1) * 2^(2n-2k-4),
implying that,
2^(2k+3) * 2^(2n-2k-4) < x^2 < 2^(2k+4) * 2^(2n-2k-4),
meaning that the number of binary digits in x^2 is 2n-1.

On the other hand, since x == 3 (mod 2^(k+2)), we have x^2 == 9 (mod
2^(k+3)), implying that x^2 starts with 9*2^(k-1). Hence,
9 * 2^(k-1) * 2^(2n-k-5) < x^2 < (9 * 2^(k-1) + 1) * 2^(2n-k-5)
or
9 * 2^(2n-6) < x^2 < 9 * 2^(2n-6) + 2^(2n-k-5),
implying that
3 * 2^(n-3) < x < 3 * 2^(n-3) + 2^(n-k-4) = (3 * 2^(k+1) + 1) * 2^(n-k-4),
implying that the binary representation of x starts with 3 * 2^(k+1). Q.E.D.

The proof is complete.

Regards,
Max

On Tue, Jul 15, 2008 at 3:28 PM,  <franktaw at netscape.net> wrote:
> Perhaps we should first ask, are there any other n for which a(n) > 1?
>  Looking
> at the way the carries work when squaring a palindrome in binary, I think
> not;
> but I don't quite see how to prove it.
>
> If the answer to this question is no, then this isn't a very interesting
> sequence
> -- it's just the characteristic sequence for binary palindromes, except a(3)
> = 3
> instead of 1.
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>
>
> I also just submitted this:
>
> %S A000001 0,3,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1
> %N A000001 a(n) = the largest integer such that n^k is palindromic in binary
> for
> all nonnegative integers k that are <= a(n).
> %C A000001 a(2n) = 0 for all n.
> %e A000001 The powers of 3 are, when written in binary: 1, 11, 1001, 11011,
> 1010001,... Now, 3^k written in binary is palindromic for k = 0,1,2, and 3,
> but
> not for k=4. So a(3) = 3.
> %O A000001 2
> %K A000001 ,more,nonn,
>
> What are the n's where a(n) is a record?
>
> Thanks,
> Leroy Quet
>
>
>
>
>
>
>
>
>
>
>
>