# 196 AND OTHER LYCHREL NUMBERS

## 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.
```