Constructing Palindromes by Reversal Addition

Def: A number palindrome is an integer that reads the same forwards and backwards. E.g., 123321

Note, single digit integers are palindromes by default. The only two digit numbers that are palindromes are 11, 22, 33, etc. Three digit palindromes are 111, 121, 131, ...., 898, 999. These numbers are not very interesting in themselves. However, if we reverse an integer and add it to itself we may obtain a palindrome. If not, we can repeat the process of reversal addition. The question is: Will we eventually obtain a palindrome if we start with an integer chosen at random.

Def: Reversal addition is the process of adding a number to itself with the digits reversed.

We can show by construction that every two digit number eventually reaches a palindrome by repeated application of reversal addition.

In the following example, we show that 89 becomes a palindrome after 24 iterations. However, after 5 iterations, the number will no longer fit into an int object. After 12 iterations the number exceeded the capacity of my calculator. After 15 iterations the number could no longer fit into a long int and hence could not be represented as an integer in the computer. Fortunately my spreadsheet program had software to handle very long integers.

It turns out that there are 13 3-digit numbers that do not produce palindromes by reversal addition after over 4K iterations. The smallest of these is 196. The conjecture is that these will never produce a palindrome, but no one has found a proof that there exists an integer which cannot produce a palindrome by repeated reversal addition for numbers in bases other than 2^k.

It should not be surprising to discover that there are numbers which are palindromic when represented in one base, but can be proved to be non palindromic when represented in base 2. The number 5642 is an example. The following table illustrates that 5642 is palindromic of order 3 in base 10.

The binary representation of 5642 is 101101000. Performing reversal addition, we get:

					    101101000
					    000101101
					    110010101
					    101010011
					   1011101000
					   0001011101
					   1101000101
					   1010001011
					  10111010000

Note that the number after 4 iterations has the same pattern as the original number except the underlined digits have doubled in size. Since the pattern repeats every 4 iterations and each of the four forms has a different outermost or next-to-outermost value, we can never reach a palindrome.

Testing numbers for palindromic behavior is very tedious. It could well use up hours of computer time. If we notice certain patterns, we can greatly reduce the number of values we have to test.

Note, all numbers whose digits are less than 5 will become palindromes on the next iteration. Also, if we compute the pair sums of a number (the sum of a digit and its corresponding digit on the other side of the number), we can divide numbers into classes. All numbers which eventually produce the same pair sums will have the same pattern in the reversal addition from that point on. Thus we need only test one number from each class to determine if the class will eventually reach a palindrome. There are only 3 3-digit classes which appear not to reach palindromes.

I am going to assign a project to my CPSC 307 students to test all 4 digit numbers for palindromic behavior. There are 9 * 10³ = 9000 different 4-digit numbers, but only 18 * 19 = 342 different pair sums.