Skip to content

Lychrel Numbers

[INITIAL SOLUTION] Lychrel Numbers

This problem can be approached in many different ways but most solutions fall into two groups:

1. Iterative solution (implemented by some form of a loop within a loop)
2. Recursive solution (a loop calling a recursive function)

The following code implements a recursive solution in Python. This problem actually lends itself nicely to a recursive solution.

The solution below was my first attempt and contains a fairly severe bug that returns a wrong (but reasonably sounding) result:

#!/usr/bin/env python

NRS_TO_CHECK = 10000

def reverse_number(number):
    return str(number)[::-1]

def is_palindrome(number):
    nr_as_string = str(number)
    reverse_as_string = reverse_number(number)
    return str(number) == reverse_as_string

def is_lychrel(number, invocation):
    if invocation > MAX_ITERATIONS:
        return True

    if is_palindrome(number):
        return False

    return is_lychrel(number + int(reverse_number(number)), invocation + 1)

lychrel_numbers = 0
for cur_number in range(1, NRS_TO_CHECK):
    if is_lychrel(cur_number, 0):
        lychrel_numbers += 1

print 'Lychrel numbers below {0}: {1}'.format(NRS_TO_CHECK, lychrel_numbers)

which returns a result of

Lychrel numbers below 10000: 246

Unfortunately, the correct result it 249. We are off by 3... can you spot the bug?

The problem is that the above code immediately returns with "not a lychrel number" if the initial number (before reversing and adding) is already a palindrome. This solution doesn't consider 4994, 8778 and 9999 to be Lychrel numbers due to the above bug.

Go on to the next page to see the final (correct) solution.

Leave a Reply

Your email address will not be published. Required fields are marked *