Antipalindromes

Tue Mar 18 22:25:45 CET 2003

I have been looking recently at numbers that are
palindromes - the same forward and backward - looking not
just at base 10, but at various bases.  In particular, I
am interested in whether a number is a palindrome in any
reasonably small base.

Some definitions:
A number n is a proper palindrome in base b if the normal
representation of n in base b is palindromic.  For
example, 5 is 101 in base 2, and thus a proper palindrome.
If n is a palindrome only when leading zeros are added, it
is an improper palindrome.  For example, 6 can be written
in base 2 as 0110, making it an improper palindrome.  
Obviously, if n is a proper palindrome in base b, n is not
divisible by b; whereas if n is an improper palindrome in
base b, it is divisble by b.

In general, a palindrome that is either proper or improper
is an extended palindrome; palindrome without
qualification means proper palindrome.

When n < b, then n is a one-digit number in base b, which
is trivially a palindrome.  More generally, if n > 2, then
n in base n-1 is the palindrome 11.  So we are interested
only in the case where b < n-1.

If n < b^2, so n is a two digit palindrome aa in base b,
then n = a(b+1).  Conversely, any composite number n > 6
can be written as a two or more digit palindrome.  (If 
n = a*b, with wlog a <= b, there are three cases.  If
a < b-1, then n is aa in base b-1.  If a = b-1, then one of
them is even, so either n = (a+1)/2 * 2a, or
n = a/2 * 2*(a+1).  Provided a > 2 (so n > 6), this is a
factorization with a < b-1, providing a two digit
palindrome.  Finally, if a = b, and a > 2 (so n > 4), then
n is 121 in base a-1.)

Thus, the primary focus is on numbers which are palindromes
in some base b with b^2 <= n.  Even looking only for proper
palindromes, it is still the case that most numbers are
palindromes by this definition.  The ones that aren't get
us the primary sequence of antipalindromes:

1,2,3,4,6,8,11,12,14,18,19,22,24,30,32,35,39,44,47,48,53,
54,58,60,66,69,70,75,76,77,79,84,87,90,94,95,96,102,103,
106,108,110,115,116,120,132,134,137,139,140,143,147,149,
152,158,159,163,167,168,174,175,176,179,180,184,187,198,
201,204,206,208,213,220,223,230,234,237,238,240,245,247,
249,254,258,263,269,270,275,279,283,293,294,296,298,304,
306,311,315,317,319,320,322,327,329,330,334,336,339,345,
347,348,352,356,359,360,367,368,370,371,380,384,389,395,
396,402,407,411,413,416,420,423,429,439,440,445,453,458,
462,466,472,475,480,486,489,490,491,500,...

Looking instead for extended palindromes, we get a somewhat
sparser list:

1,2,3,11,19,22,35,44,47,53,58,70,76,77,79,87,94,95,103,106,
115,134,137,139,140,143,149,158,159,163,167,174,175,176,
179,187,201,206,208,213,223,237,247,249,263,269,275,279,
283,293,296,298,304,311,315,317,319,322,327,329,334,339,
345,347,348,352,356,359,367,368,370,371,389,395,407,411,
413,416,423,429,439,445,458,466,472,475,489,491,...

The third antipalindrome sequence comes when we allow any
b < n-1:

1,2,3,4,6,11,19,47,53,79,103,137,139,149,163,167,179,223,
263,269,283,293,311,317,347,359,367,389,439,491,563,569,
593,607,659,739,827,853,877,977,983,997,1019,1049,1061,
1187,1213,1237,1367,1433,1439,1447,1459,1511,1553,1579,
1669,1709,1753,1759,1907,1949,1993,1997,2011,2063,2087,
2099,2111,2137,2179,2207,2287,2309,2339,2417,2459,2503,
2657,2677,2683,2693,2713,2749,2897,2963,3023,3089,3119,
3229,3253,3259,3323,3371,3407,3449,3547,3559,3583,3623,
3643,3833,3847,4007,4073,4091,4099,4139,4157,4211,4283,
4337,4339,4349,4391,4463,4523,4549,4643,4679,4729,4787,
4871,4909,4919,4933,...

Based on the comments above about factorization, further
restricting the sequence by allowing improper palindromes
gives us a fourth sequence, which differs from the first
only by the ommission of 4 and 6:

1,2,3,11,19,47,53,79,...

(It is ironic that the smallest non-trival antipalindrome
of this type is 11, which is a palindrome in base 10.)

Finally, we can look only at prime antipalindromes, which
is this fourth sequence with 1 also omitted.

I plan to submit these sequences to the OEIS, and also
some others relating to palindromes.  I have a couple of
questions I want to ask first; two relating to the OEIS
itself, and the rest mathematical.

1. Should I add the fourth and/or fifth sequences, or just
the first three?

2. I think that these should be added without the "base"
keyword, since they do not relate to representation of the
numbers in any particular base.  Is this correct?

3. (The $64,000 question.)  Can anyone prove that the first
sequence is infinite?  A simple probabilistic argument is
to note that the probability that n is a palindrome in base
b is approximately sqrt(n), and we are looking at sqrt(n)
bases, so assuming a random distribution, about 1/e numbers
should be antipalindromes.  A slightly more sophisticated
argument, focussing on the 3 digit palindromes, suggests
that the density should go to zero, but there should still
be infinitely many of them.  Experimental results up to
10,000 are consistent with this latter result.  However, I
don't have any idea how to prove this.  

4. The same question for the second sequence is very 
similar.

5. Is the third sequence infinite?  Here the density must
be zero, since all but finitely many values are prime.
The probabilistic argument still suggests that there should
be infinitely many prime antipalindromes.

6. Once the above questions have been answered, one can
ask about the distributions of these sequences.

-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645

__________________________________________________________________
Try AOL and get 1045 hours FREE for 45 days!
http://free.aol.com/tryaolfree/index.adp?375380

Get AOL Instant Messenger 5.1 for FREE! Download Now!
http://aim.aol.com/aimnew/Aim/register.adp?promos=380455