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] 12I 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 341It'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 etcI 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.