Another Sequence Related To Binary Palindromes

[Max Alekseyev]

It must be added to the cases i) and iii) that "..." in the forms
"100...001" and "11...11" hides at least one digit 1. That follows
from the trivial observation that (2^n + 1)^2 or (3*2^n + 3)^2 for n>1
are not palindromic-in-binary.

Regards,
Max

On Wed, Jul 16, 2008 at 11:27 PM, Max Alekseyev <maxale at gmail.com> wrote:
> 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
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>



>* Olivier Gerard <olivier.gerard at gmail.com> [Jul 17. 2008 11:05]:
>> [...]
>
>> 
>> Neil: in the same spirit as the "more" keywords, you could
>> perhaps create one or several keywords to signal older sequences
>> needing examples or self-contained definitions (this would be
>> different from the "uned" keyword). This would help focusing teamwork
>> on these eventually.
>
>I strongly support this ("need self contained definition", and
>"need examples").

This can done in Comment lines, like this:

%C A987654 Needs self-contained definition.
%C A987654 Needs examples.
%C A987654 Needs a b-file.

As long as we always use roughly the same wording, it will
be easy to search for such lines.

Neil




Hans, You said:
Last year I submitted a ten-thousand value "b-file" for A036236. The  
link to it says only one-thousand: that can be fixed.

value of a(69) is presently unknown, and your file gives the value
of -1 for n=69.

That's why the link looks like this:

%H A036236 Hans Havermann, <a href="http://www.research.att.com/~njas/sequences/a036236.txt">Ta\
ble of n, a(n) for n = 1..1000 with -1 for those entries where a(n) > 10^11</a>

The file is called a036236.txt (not b036236.txt) - and that's probably why
i shortened it to 1000 terms from 10000.

You also said:

For A078457, Why is a(0) = 3, and not 1?


Best regards

Neil