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

 

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 reverse-sum 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 palindrome-free 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 reverse-sum 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 reverse-sum 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 palindrome-free sequence with the following six-step cycle

 

 

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

 

 

Likewise for the base B = 16 = 24 we have the 2(4+1) = 10-step 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 self-similar cycles, beyond those in this infinite family. One example is this four-cycle 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 palindrome-free sequences in each base from 2 through 19 are listed below (in decimal):

 

 

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

 

 

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 quasi-periodicity of order 8. In fact, sequence "C" in the table above shows this quasi-periodicity, beginning with 1750067. For more on this, see Self-Similar Reverse-Sum Sequences.

 

Return to MathPages Main Menu