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 

_{} 

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

It's worth noting that, if there were no carries in the addition, every number produced by adding a number to its reversal would be a palindrome. In fact, even with carries, it's easy to see that each digit of a number produced in this way can differ from the reflected digit by no more than 1. Compare, for example, the digits and reflected digits of the 4th from the last number in the sequence above 

_{} 

This near palindromicity follows immediately from the fact that each digit and its reflection are both the sums of the same two digits, so the only way they can differ is if one involves a "carry" and the other doesn't. A carry is only a single unit, so the reflected digits can differ by (at most) only a unit from each other. 

Despite the natural tendancy for the reversesum operation to produce palindromes, some sequences of reverse sums, such as the one beginning with the number 196, evidently never yield a perfect palindrome. We say "evidently" because it has not been proven, but millions of terms of the "196 sequence" have been computed without ever reaching a palindrome. In fact, no one has ever proven that any number leads to an infinite sequence of palindromefree numbers in the base 10. 

On the other hand, 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 reversesum sequence beginning with 10110 is 

_{} 

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

_{} 

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

_{} 

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 palindromefree sequence with the following sixstep cycle 

_{} 

A similar cycle exists for every base that is a power of two. In particular, if B = 2^{k} then there is a cycle of length 2(k+1). For example, with the base B = 8 we have the eightstep cycle exemplified by the terms below 

_{} 

Likewise for the base B = 16 = 2^{4} we have the 2(4+1) = 10step cycle exemplified by the terms shown below. 

_{} 

The pattern for these powers of two is shown by taking representative terms from each cycle: 

_{} 

and so on. In addition, there exist other selfsimilar cycles, beyond those in this infinite family. One example is this fourcycle in the base 2: 

_{} 

Another example for the base 2 is shown below: 

_{} 

There are also a few sporadic examples in bases other than powers of 2, as shown by David Seal. However, no one knows how to construct a similar example for the base 10. 

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

_{} 

It's interesting that, in each base, all the palindromefree 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 palindromefree sequences. The initial values of these sequences are 

_{} 

Could it be that 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. Some sequences in the base 3 seem to exhibit a degree of period near 13. Likewise in the base 10 there exist sequences with quasiperiodicity of order 8. In fact, sequence "C" in the table above shows this quasiperiodicity, beginning with 1750067. For more on this, see SelfSimilar ReverseSum Sequences. 
