Solution

Answer: 249

A Lychrel number (for the purposes of this problem) is a number that does not become palindromic within 50 iterations of the “reverse-and-add” process.

We must count how many integers $1 \le n < 10000$ are Lychrel numbers under this definition.

Mathematical analysis

For a positive integer $n$:

Reverse its decimal digits:

$$r(n)$$ 2. Form:

$$n_1 = n + r(n)$$ 3. If $n_1$ is a palindrome, stop. 4. Otherwise repeat.

We classify $n$ as a Lychrel number if no palindrome appears within 50 iterations.

Example 1: $47$

$$47 + 74 = 121$$

Since $121$ is a palindrome, $47$ is not Lychrel.

Example 2: $349$

$$349 + 943 = 1292$$

$$1292 + 2921 = 4213$$

$$4213 + 3124 = 7337$$

After 3 iterations we obtain the palindrome $7337$, so $349$ is not Lychrel.

Key observations

1. Detecting palindromes

A number is palindromic if its decimal representation equals its reverse.

For example:

$121 \rightarrow$ palindrome
$7337 \rightarrow$ palindrome
$123 \rightarrow$ not palindrome

Algorithmically:

s == s[::-1]

2. Reverse-and-add operation

$$n = 1234$$

then

$$r(n)=4321$$

and

$$1234+4321=5555$$

3. Iteration limit

The problem explicitly states:

every number below $10000$ either:
becomes palindromic in fewer than 50 iterations, or
is considered Lychrel for this problem.

So we only need to test at most 50 iterations.

Algorithm

For each number $n$ from $1$ to $9999$:

Set $x=n$
Repeat up to 50 times:

compute:

$$x \leftarrow x + r(x)$$

if $x$ is a palindrome:
$n$ is not Lychrel
stop

If no palindrome appears after 50 iterations:

count $n$ as Lychrel

Python implementation

def reverse_number(n):
    """Return the integer obtained by reversing decimal digits of n."""
    return int(str(n)[::-1])

def is_palindrome(n):
    """Check whether n is a palindrome."""
    s = str(n)
    return s == s[::-1]

def is_lychrel(n, limit=50):
    """
    Return True if n is considered a Lychrel number.
    
    We repeatedly apply reverse-and-add up to 'limit' times.
    If a palindrome appears, return False.
    Otherwise return True.
    """
    x = n

    for _ in range(limit):
        x = x + reverse_number(x)

        if is_palindrome(x):
            return False

    return True

# Count Lychrel numbers below 10000
count = 0

for n in range(1, 10000):
    if is_lychrel(n):
        count += 1

print(count)

Code walkthrough

`reverse_number`

def reverse_number(n):
    return int(str(n)[::-1])

Convert integer to string
Reverse characters using slicing
Convert back to integer

Example:

reverse_number(349)

gives:

`is_palindrome`

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

Checks whether the string reads identically forwards and backwards.

Examples:

is_palindrome(121)   -> True
is_palindrome(123)   -> False

`is_lychrel`

for _ in range(limit):

We perform at most 50 reverse-add iterations.

Each step:

x = x + reverse_number(x)

Then test:

if is_palindrome(x):
    return False

If a palindrome appears, the number is not Lychrel.

If the loop finishes without success:

return True

Final counting loop

for n in range(1, 10000):

Tests every positive integer below 10000.

Whenever is_lychrel(n) is true, increment the counter.

Verification on examples

$47$

Iteration:

$$47+74=121$$

Palindrome immediately found.

So:

is_lychrel(47) -> False

Correct.

$349$

Sequence:

$$349 \to 1292 \to 4213 \to 7337$$

Palindrome after 3 iterations.

So:

is_lychrel(349) -> False

Correct.

Final verification

The number of Lychrel candidates below $10000$ is known to be relatively small (a few hundred), so the result should be of moderate size.

Running the algorithm carefully gives:

$$249$$

This is consistent with known Project Euler results.

Answer: 249

Project Euler Problem 55