Lychrel Numbers

If we take $47$, reverse and add, $47 + 74 = 121$, which is palindromic.
Not all numbers produce palindromes so quickly. For example,
\begin{align}
349 + 943 &= 1292\\
1292 + 2921 &= 4213\\
4213 + 3124 &= 7337
\end{align}
That is, $349$ took three iterations to arrive at a palindrome.
Although no one has proved it yet, it is thought that some numbers, like $196$, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, $10677$ is the first number to be shown to require over fifty iterations before producing a palindrome: $4668731596684224866951378664$ ($53$ iterations, $28$-digits).
Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is $4994$.
How many Lychrel numbers are there below ten-thousand?
NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

To tackle this problem, you can write a code to compute the Lychrel numbers. Here is a pseudocode for how this computation could be done, but you have to understand that it’s a brute force approach.

Possible pseudocode:

“`
Initialize counter as 0
For each number in range(1, 10000):
Declare num as int
For i in range(50):
Reverse the number (convert to str, use slicing, convert back to int)
Add the number to its reverse
if the result is a palindrome:
skip to the next number in the outer loop
When the inner loop finishes, increment the counter
Print counter
“`

Explanation:

1. We initialize a counter to store how many Lychrel numbers we find.

2. Then we iterate over all numbers from 1 to 10,000 (since we’re looking for Lychrel numbers below 10,000).

3. For each number, we perform the “reverse and add” operation up to 50 times (as per the problem statement).

4. If at any point the result is a palindrome, we know this number is not a Lychrel number and we move on to the next number.

5. If after 50 iterations we have not found a palindrome, we assume the number is a Lychrel number and increment our counter.

6. Finally, we print the counter which stores the total number of Lychrel numbers below 10,000.

This is a simple way (brute force way) to solve the problem but due to the lack of a proven mathematical theory on Lychrel numbers, it’s the most appropriate one.

To actually execute this pseudocode, you will need to use a programming language such as Python or Java.

However, you must note that while this pseudocode assumes that numbers which do not produce a palindrome in 50 iterations are Lychrel numbers, no number has been proven to be a Lychrel number — it remains an open question in number theory.

More Answers: