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.
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
176881317877
778713188671
-------------
1010100010101
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
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
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 eight-step cycle exemplified by the terms below
22000000000655577777777712 22 9*0 6555 9*7 12
44000000000433377777777734
107777777777767000000000000
110000000000756777777777701
220000000000635777777777712
440000000000373777777777734
1077777777777767000000000000
1100000000007666777777777701
2200000000006555777777777712 22 10*0 6555 10*7 12
Likewise for the base B = 16 = 2^4 we have the 2(4+1) = 10-step cycle
exemplified by the terms shown below.
8800000008777fffffff78 88 7*0 8777 7*f 78
10fffffffffef0000000000
1100000000fdeffffffff01
2200000000ebdffffffff12
4400000000c7bffffffff34
88000000007f7ffffffff78
10ffffffffffef0000000000
1100000000feeeffffffff01
2200000000edddffffffff12
4400000000cbbbffffffff34
88000000008777ffffffff78 88 8*0 8777 8*f 78
The pattern for these powers of two is shown by taking representative terms
from each cycle:
Base 2: 10 [n1] 01 [n0]
Base 4: 10 [n3] 23 [n0]
Base 8: 10 [n7] 67 [n0]
Base 16: 10 [nf] ef [n0]
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:
10 111111111111 0100000101111101 0000000000 00
11 0000000000 100011101110001000 1111111111 01
10 111111111111 0100000101111101 00000000000 00
11 000000000000 1011111010000010 11111111111 01
10 1111111111111 0100000101111101 00000000000 00
Another example for the base 2 is shown below:
11 000000000 00011010 111111111 01
10 1111111111 01110011 000000000 00
11 000000000 100010000 111111111 01
10 1111111111 10010001 0000000000 00
11 0000000000 00011010 1111111111 01
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):
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
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