Homepage

196 AND OTHER LYCHREL NUMBERS

Random Quote

Site Links

Welcome to p196.org!

Originally found at: http://203.162.7.73/webs/math/mathpages/www.seanet.com/~ksbrown/kmath004.htm
Digit Reversal Sums Leading to Palindromes
Beginning with the decimal representation of any integer N, reverse 
the digits and add it to N.  Iterate this operation.  Typically you 
will soon arrive at a palindrome, i.e., a number that reads the same 
forwards and backwards.  For example, starting with 39, we have 
39 + 93 = 132.  Then 132 + 231 = 363 = palindrome.

Some numbers take a long time to yield a palindrome.  For example, 
the sequence beginning with 89 is

                      89      ------>   159487405
                     187     |          664272356
                     968     |         1317544822
                    1837     |         3602001953
                    9218     |         7193004016
                   17347     |        13297007933
                   91718     |        47267087164
                  173437     |        93445163438
                  907808     |       176881317877
                 1716517     |       955594506548
                 8872688     |      1801200002107
                17735476     |      8813200023188  =  palindrome!
                85189247 --->

(Interestingly, there are twelve numbers less than 1000 for which the
reverse-sum sequence leads to the palindrome 8813200023188, one of 
which, 484, is itself a palindrome.  These are the longest finite 
sequences in this range.)

The number 196 evidently NEVER yields a palindrome, although this has 
never been proven.  In fact, no one knows for sure if ANY number leads
to an infinite sequence of palindrome-free numbers in the base 10.

However, it isn't hard to prove the existence of sequences that never 
produce a palindrome in certain other bases.   For example, the smallest 
number that never becomes palindromic in the base 2 is 10110 (decimal 
22).  To prove this, first observe that the reverse-sum sequence 
beginning with 10110 is

                          10110
                         100011
                        1010100
                        1101001
                       10110100
                          etc
                          

The last term quoted above is 10110100, which is of the form

                        10 [n*1] 01 [n*0]

where the symbol [n*x] signifies n consecutive occurences of the digit
x.  By simple arithmetic we can demonstrate that the reverse-sum
sequence beginning with any number of this form proceedes as follows

                               10 [n*1] 01 [n*0]
                  11 [(n-2)*0] 1000 [(n-2)*1] 01
                           10 [n*1] 01 [(n+1)*0]
                        11 [n*0] 10 [(n-1)*1] 01
                       10 [(n+1)*1] 01 [(n+1)*0]

The last representation is identical to the first, except that n 
has been replaced by n+1.  By induction, it follows that the entire 
sequence consists of repetitions of this cycle, and none of the 
elements are palindromes.

In the base 4, the number 255 (decimal) leads to a palindrome-free
sequence with the following six-step cycle

                            22 [n*0] 131 [n*3] 12
                        10 [(n+2)*3] 23 [(n+2)*0]
                           11 [n*0] 3222 [n*3] 01
                           22 [n*0] 2111 [n*3] 12
                        10 [(n+2)*3] 23 [(n+3)*0]
                    11 [(n+1)*0] 312 [(n+1)*3] 01
                    22 [(n+1)*0] 131 [(n+1)*3] 12

I believe similar arguments work for any base that is a power of 2,
and for certain other selected bases, but evidently no one knows how 
to construct a similar argument for the base 10.

Empirically, the smallest numbers leading to palindrome-free sequences 
in each base from 2 through 19 are listed below (in decimal):

        2     22          8   1021          14   361
        3    100          9    593          15   447
        4    255         10    196          16   413
        5    708         11   1011          17  3297
        6   1079         12    237          18   519
        7   2656         13   2196          19   341

It's interesting that, in each base, all the palindrome-free sequences
converge very rapidly on just a small number of sequences.  For example,
in the base 10 there are 63 numbers less than or equal to 4619 that 
(evidently) never become palindromic, and these 63 numbers each lead to 
one of only three palindrome-free sequences.  The initial values of 
these sequences are

                 A             B              C

                887          1857           9988
               1675          9438          18887
               7436         17787          97768
              13783         96558         184547
              52514        182127         930028
              94039        903408        1750067
             187088       1707717        9350638
            1067869       8884788       17711177
               etc           etc           etc

I suspect these sequence are cyclical (in the sense of the base
2 and base 4 cycles described above), but with irrational periods.
Notice that each term in the sequence can be regarded as a sort of
"convolution" of the preceeding term, and there are known examples 
of sequences based on convolution that are cyclical with irrational
periods.  (In the base 3 the period seems to be near 13.)

For more on this topic, see Self-Similar Reverse-Sum Sequences.
Also, see David Seal's Results.