Another Sequence Related To Binary Palindromes

Jack Brennen jb at
Wed Jul 16 02:05:30 CEST 2008

Heuristically, we can approximate the number of such numbers which
are binary palindromes along with their squares being binary
palindromes.  For a random odd number N with B binary bits, the
probability that it is a palindrome is roughly 1/2^(B/2).  The
probability that its square is a palindrome is roughly 1/2^B.
(We're assuming here that the bits in the square are basically
random, which may not be true of course.)

Multiply them together, you get 1/2^(3*B/2).  B is roughly equal
to log(N)/log(2), giving us an approximate probability of 1/N^(3/2)
for the dual hit of a palindromic N and a palindromic N^2.

The sum of 1/N^(3/2) over all odd N from 3 to infinity is somewhere
around 0.688.  Which would lead us to believe that the number of
N such that N and N^2 are both binary palindromes is most likely
to be equal to 1.  Well, we know what that one is (N=3); there are
most likely no more unless our hypothesis that the bits of the
square are statistically random is significantly off the mark...

By the way, if anyone wants to do a search for squares which are
binary palindromes, take advantage of the fact that the form of
the binary palindrome square must be 100......001.  So if you are
systematically working your way up through the squares, once the
top three bits carry over to being 101, you can take a big jump
forward to 1000.  Essentially, over 71% of the candidates are
skipped trivially because their first three digits are 101, 110,
or 111.


franktaw at 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>
> 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

More information about the SeqFan mailing list