A104444

[David Wilson]

My newly-submitted A104444 purports to give numbers that are not
the difference of two palindromes.  You asked how I could be
sure that a given number was not the difference of two large
palindromes.  Here is my reasoning, there are empirical parts,
but I think it all could be proved rigorously if necessary.

Let p(n) be the nth palindrome, e.g, p(0) = 0, p(1) = 1, ...,
that is p(n) = A002113(n).

Let q(n) = p(n+1)-p(n) be the difference between two adjacent
palindromes.  We can show that

  Theorem 1: d(n) = p(n+1)-p(n) must be either 2, of the form
    10^k (k >= 0), or of the form 11*10^k (k >= 0).

This is, d(n) is in the sequence

   1, 2, 10, 11, 100, 1100, 1000, 1100, 10000, 11000, ...

recently submitted as A104459.

Define

  s(d) =
    10^((d-1)/2)         if d is odd
    11*10^((d-2)/2)    if d is even.

The first few values are

   d    s(d)
   1       1
   2      11
   3      10
   4     110
   5     100
   6    1100
   7    1000
   8   11000
   9   10000
   etc.

s(d) is the "characteristic difference" of d-digit palindromes,
that is two adjacent d-digit palindromes usually differ by s(d).
Specifically, we can show that 

  Theorem 2:  Let p(n) have d >= 2 digits.
    If n !== 8 (mod 10), q(n) = p(n+1)-p(n) = s(d).

In other words, the difference q(n) between the two adjacent
d-digit palindromes p(n) and p(n+1) will be s(d) except for
every tenth difference (when n == 8 (mod 10)) which will be
some other element of A104459.

------------------------------------------------------------
Let z >= 0.  Suppose we wish to determine whether z is the
difference to two palindromes.

Let dmin = 2*floor(log10(z)+1) = 2*(number of digits of z).
dmin is the least value such that d >= dmin implies s(d) > z.

Let p(n) be a palindrome of d >= dmin digits.  d >= dmin
implies s(d) > z and s(d+1) > z.  Also, p(n+1) is a
palindrome of either d or d+1 digits.

Now either n !== 8 (mod 10) or n+1 != 8 (mod 10).
If n !== 8 (mod 10), p(n+1)-p(n) = s(d) > z.
If n+1 !== 8 (mod 10), p(n+2)-p(n+1) = s(d) > z
or p(n+2)-p(n+1) = s(d+1) > z.  Either way, we have
p(n+2)-p(n) > z.

In other words, for any palindrome p(n) of d >= dmin digits,
we have p(n+2)-p(n) > z ==> p(n+k)-p(n) > z for k >= 2.  This
means that if z is the difference of two such palindromes, it
is of the form p(n+1)-p(n), that is, the difference of two
adjacent palindromes.  By theorem 1, z must be in A104459.

But if z is in A104459, it is the difference of two palindromes
with < dmin digits.  The following table shows how:

         z  dmin  difference

         1     2  1-0
         2     2  2-0
        10     4  11-1
        11     4  11-0
       100     6  101-1
       110     6  111-1
      1000     8  1001-1
      1100     8  1111-11
     10000    10  10001-1
     11000    10  11011-11
    100000    12  100001-1
    110000    12  110011-11

The pattern is obvious and can be extended to z of any number
of digits.

So, to tell if z is the difference of two palindromes, it
suffices to check if z = p(n+k)-p(n), where p(n) is a
palindrome of d < dmin = 2*(number of digits in z) digits.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050309/89fb3639/attachment.htm>