Palindromes

Palindromes are words or numbers that read the same both forwards and backwards. Examples of words that are palindromes are "noon" and "rotator". An example of a sentence that is a palindrome is "A man, a plan, a canal - Panama!". Palindromic numbers are numbers that read the same forwards and backwards, such as 55, 747, or 3883.

If you have a number that is not a palindrome, you often can create a palindrome by doing the following: Reverse the number's digits and add the result to the original number. Repeat the process until you get a palindrome. For example, 76 + 67 = 143. 143 + 341 = 484, which is a palindrome. Some numbers take a bit longer. The number 89 takes 24 iterations of this process until a palindrome is reached.

Pick a few numbers yourself and see what the result is.

Do all numbers become palindromes eventually? The answer to this question is not known. 196 is the smallest number for which this process never seems to produce a palindrome. This process has been repeated the number 196 for one billion iterations, producing a number with over 400 million digits, without any success. It seems that 196 never produces a palindrome, but no proof has been found that it never does. Numbers that never seem to become palindromes are called Lychrel numbers.

With the advent of computers, it's become much easier to work on this problem. It appears that all numbers either become a palindrome within a few hundred iterations or so, or they never become a palindrome. The number 1,186,060,307,891,929,990 becomes a palindrome after 261 iterations; no number is yet known that takes more iterations to become a palindrome. The most delayed palindrome I've personally found is 714,773,441,995,247,560,985,416, which takes 201 iterations.

The next few paragraphs are somewhat speculative, but are worthwhile reading if you want to think deeply about the problem. If not, they can be safely skipped.

If you think about it, it seems reasonable that no numbers are known that produce a palindrome after a very large number of iterations. The percentage of numbers that are palindromes decreases as the number of digits increases. All numbers with just one digit are palindromes. 10% of numbers with two or three digits are palindromes. 1% of numbers with four or five digits are palindromes, and this number would continue to drop by a factor of 10 with every increase of two digits. The odds that a random 100-digit number would be a palindrome are astronomically small.

But does the algorithm of reversing the digits and adding perform something special that would make the chance of a palindrome appearing better than chance? Well, it does if the number is such that reversing and adding would not produce any carries in the addition. If there are no carries, the number will always be a palindrome. However, this is very unlikely the larger the numbers get. If you're adding a 100-digit number to its reverse, you would need 50 pairs of numbers all of which sum to 9 or less, which seems very unlikely as well.

Apart from the above scenario, does the algorithm do something special to make it likely that a palindrome would result? My guess would have to be no. It is quite successful with smaller numbers, but that may just be because a relatively large percentage of smaller number happen to be palindromes, so when you add any two small numbers together you may just get a palindrome. It would be interesting to try different algorithms and see whether they are any better or worse at producing palindromes.