<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2900.2604" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY>
<DIV><FONT face="Courier New" size=1>My newly-submitted A104444 purports to give
numbers that are not</FONT></DIV>
<DIV><FONT face="Courier New" size=1>the difference of two palindromes.
You asked how I could be</FONT></DIV>
<DIV><FONT face="Courier New" size=1>sure that a given number was not the
difference of two large</FONT></DIV>
<DIV><FONT face="Courier New" size=1>palindromes. Here is my reasoning,
there are empirical parts,</FONT></DIV>
<DIV><FONT face="Courier New" size=1>but I think it all could be proved
rigorously if necessary.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>Let p(n) be the nth palindrome, e.g, p(0) =
0, p(1) = 1, ...,</FONT></DIV>
<DIV><FONT face="Courier New" size=1>that is p(n) = A002113(n).</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>Let q(n) = p(n+1)-p(n) be the difference
between two adjacent</FONT></DIV>
<DIV><FONT face="Courier New" size=1>palindromes. We can show
that</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1> Theorem 1: </FONT><FONT
face="Courier New" size=1>d(n) = p(n+1)-p(n)</FONT><FONT face="Courier New"
size=1> must be either 2, of the form</FONT></DIV>
<DIV><FONT face="Courier New" size=1> 10^k (k >= 0),
or of the form 11*10^k (k >= 0).</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>This is, d(n) is in the
sequence</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1> 1, 2, 10, 11, 100, 1100, 1000,
1100, 10000, 11000, ...</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>recently submitted as A104459.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>Define</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1> s(d) =</FONT></DIV>
<DIV><FONT face="Courier New" size=1>
10^((d-1)/2) if d is
odd</FONT></DIV>
<DIV><FONT face="Courier New" size=1> 11*10^((d-2)/2)
if d is even.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>The first few values are</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1> d
s(d)</FONT></DIV>
<DIV><FONT face="Courier New" size=1>
1 1</FONT></DIV>
<DIV><FONT face="Courier New" size=1>
2 11</FONT></DIV>
<DIV><FONT face="Courier New" size=1>
3 10</FONT></DIV>
<DIV><FONT face="Courier New" size=1>
4 110</FONT></DIV>
<DIV><FONT face="Courier New" size=1> 5
100</FONT></DIV>
<DIV><FONT face="Courier New" size=1>
6 1100</FONT></DIV>
<DIV><FONT face="Courier New" size=1> 7
1000</FONT></DIV>
<DIV><FONT face="Courier New" size=1> 8
11000</FONT></DIV>
<DIV><FONT face="Courier New" size=1> 9
10000</FONT></DIV>
<DIV><FONT face="Courier New" size=1> etc.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>s(d) is the "characteristic difference" of
d-digit palindromes,</FONT></DIV>
<DIV><FONT face="Courier New" size=1>that is two adjacent d-digit palindromes
usually differ by s(d).</FONT></DIV>
<DIV><FONT face="Courier New" size=1>Specifically, we can show that
</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1> Theorem 2: Let p(n) have
d >= 2 digits.</FONT></DIV>
<DIV><FONT face="Courier New" size=1> If n !== 8 (mod
10), q(n) = p(n+1)-p(n) = s(d).</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>In other words, the difference q(n) between
the two adjacent</FONT></DIV>
<DIV><FONT face="Courier New" size=1>d-digit </FONT><FONT face="Courier New"
size=1>palindromes p(n) and p(n+1) will be s(d) except for</FONT></DIV>
<DIV><FONT face="Courier New" size=1>every tenth difference (when n == 8 (mod
10)) which will be</FONT></DIV>
<DIV><FONT face="Courier New" size=1>some other element of A104459.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New"
size=1>------------------------------------------------------------</FONT></DIV>
<DIV><FONT face="Courier New" size=1>Let z >= 0. Suppose we wish to
determine whether z is the</FONT></DIV>
<DIV><FONT face="Courier New" size=1>difference to two palindromes.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>Let dmin = 2*floor(log10(z)+1) = 2*(number
of digits of z).</FONT></DIV>
<DIV><FONT face="Courier New" size=1>dmin is the least value such that d >=
dmin implies </FONT><FONT face="Courier New" size=1>s(d) > z.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>Let p(n) be a palindrome of d >= dmin
digits. d >= dmin</FONT></DIV>
<DIV><FONT face="Courier New" size=1>implies </FONT><FONT
face="Courier New" size=1>s(d) > z and s(d+1) > z. Also, p(n+1) is
a</FONT></DIV>
<DIV><FONT face="Courier New" size=1>palindrome of either d or d+1
digits.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>Now either n !== 8 (mod 10) or n+1 != 8
(mod 10).</FONT></DIV>
<DIV><FONT face="Courier New" size=1>If </FONT><FONT face="Courier New" size=1>n
!== 8 (mod 10), p(n+1)-p(n) = s(d) > z.</FONT></DIV>
<DIV><FONT face="Courier New" size=1>If n+1 !== 8 (mod 10), p(n+2)-p(n+1) = s(d)
> z</FONT></DIV>
<DIV><FONT face="Courier New" size=1>or p(n+2)-p(n+1) = s(d+1) > z.
Either way, we have</FONT></DIV>
<DIV><FONT face="Courier New" size=1>p(n+2)-p(n) > z.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>In other words, for any palindrome p(n) of
d >= dmin digits,</FONT></DIV>
<DIV><FONT face="Courier New" size=1>we have p(n+2)-p(n) > z ==>
p(n+k)-p(n) > z for k >= 2. This</FONT></DIV>
<DIV><FONT face="Courier New" size=1>means that if z is the </FONT><FONT
face="Courier New" size=1>difference of two such palindromes, it</FONT></DIV>
<DIV><FONT face="Courier New" size=1>is of the form p(n+1)-p(n), that is, the
difference of two</FONT></DIV>
<DIV><FONT face="Courier New" size=1>adjacent palindromes. </FONT><FONT
face="Courier New" size=1>By theorem 1, </FONT><FONT face="Courier New" size=1>z
must be in </FONT><FONT face="Courier New" size=1>A104459.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>But if z is in A104459, it is the
difference of two palindromes</FONT></DIV>
<DIV><FONT face="Courier New" size=1>with < dmin digits. The following
table shows how:</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV>
<DIV><FONT face="Courier New"
size=1> z dmin
difference</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face="Courier New"
size=1>
1 2
1-0<BR>
2 2
2-0<BR> 10
4 11-1<BR>
11 4 11-0<BR>
100 6
101-1<BR> 110
6 111-1<BR> 1000
8 1001-1<BR> 1100
8 1111-11<BR> 10000 10
10001-1<BR> 11000 10
11011-11<BR> 100000 12
100001-1<BR> 110000 12
110011-11</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV>
<DIV><FONT face="Courier New" size=1>The pattern is obvious and can be extended
to z of any number</FONT></DIV>
<DIV><FONT face="Courier New" size=1>of digits.</FONT></DIV>
<DIV><FONT face="Courier New" size=1></FONT> </DIV></DIV>
<DIV><FONT face="Courier New" size=1>So, to tell if z is the difference of two
palindromes, it</FONT></DIV>
<DIV><FONT face="Courier New" size=1>suffices to check if z = p(n+k)-p(n), where
p(n) is a</FONT></DIV>
<DIV><FONT face="Courier New" size=1>palindrome of d < dmin = 2*(number of
digits in z) digits.</FONT></DIV></BODY></HTML>