Lychrel calculator (Project Euler 55)

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.


Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

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?

This is my solution:

```
from datetime import datetime

candidates = []

def reverse(number):
''' Returns the reverse order of an integer,
for example: reverse(123) returns the integer 321 '''
number = str(number)
return int(number[::-1])

def is_lychrel(number):
''' Returns True if 'number' is a lychrel candidate,
but works only with numbers from 1 to 10000 '''
iterated = number + reverse(number)
for i in range(25):
rev_iterated = reverse(iterated)
if iterated != rev_iterated:
iterated = iterated + rev_iterated
else:
return False
return True

if __name__ == '__main__':

start_time = datetime.now()

for number in range(10001):
if is_ly

1. Comments on your code

-
Python has a built-in module, timeit, for measuring the execution time of small code snippets. So there is no need for all that fussing about with datetime.

-
Project Euler problem 55 says:


you are given that for every number below ten thousand, it will either (i) become a palindrome in less than fifty iterations

but your code only tries 25 iterations. It happens to be the case that 25 iterations are enough in this case, but how did you figure that out? If you had a mathematical proof that showed that 25 iterations were enough, then that would be fair enough, but I suspect that in fact you re-ran the program with different values for the count of iterations until you found that smallest one that produces the right answer. This seems like cheating to me: if you are willing to do that, why not just replace the whole program with:

print(answer)

which would be even faster?

-
The problem statement asks:


How many Lychrel numbers are there below ten-thousand?

but you test range(10001) which is off by one. Luckily for you, 10,000 is not a Lychrel number, so this doesn't lead to an error.

-
You've made candidates into a global variable, and run some of your code at top level. This makes it hard to test your program from the interactive interpreter. You need something like this:

def problem55(n):
    """Return a list of Lychrel candidates below n."""
    candidates = []
    for number in range(n):
        if is_lychrel(number):
            candidates.append(number)
    return candidates

and then you can test it like this:

>>> from timeit import timeit
>>> timeit(lambda:problem55(10000), number=100)
8.279778157011606

1. Speeding it up

-
The problem statement only asks how many Lychrel numbers there are, so there is no need to construct a list of them.

-
Function calls in Python are moderately expensive, so you can save some time by inlining them. This leads to an implementation like this:

def problem55_1(n, m):
    """Return the count of numbers below n that do not lead to a
    palindrome after m iterations of reversal and addition.

    """
    count = 0
    for i in range(n):
        r = int(str(i)[::-1])
        for _ in range(m):
            i += r
            r = int(str(i)[::-1])
            if i == r:
                break
        else:
            count += 1
    return count

which is about 16% faster than yours:

>>> timeit(lambda:problem55_1(10000, 50), number=100)
6.93482669594232

-
Janne suggested that you could speed things up by caching the numbers already found to be Lychrel and non-Lychrel, and you replied:


doing that is going to require more conditions and probably is going to be the same running time or even worse

which is a bit of a defeatist attitude. Certainly the code gets more complex when you add caching, but it's not a priori obvious whether this costs more than it saves, or saves more than it costs. The best way to find out is to knuckle down and try it:

def problem55_2(n, m):
    """Return the count of numbers below n that do not lead to a
    palindrome after m iterations of reversal and addition.

    """
    lychrel = set()
    nonlychrel = set()
    count = 0
    for i in range(n):
        j = i
        if i in lychrel:
            count += 1
            continue
        stack = [i]
        r = int(str(i)[::-1])
        for _ in range(m):
            i += r
            if i in lychrel:
                count += 1
                lychrel.update(stack)
                break
            if i in nonlychrel:
                nonlychrel.update(stack)
                break
            stack.append(i)
            r = int(str(i)[::-1])
            if i == r:
                nonlychrel.update(stack)
                break
        else:
            count += 1
            lychrel.update(stack)
    return count

I find that this is about twice as fast as your code:

>>> timeit(lambda:problem55_2(10000, 50), number=100)
3.935654202941805

-
One final tweak from me. Now that we are caching, the order in which we check numbers for the Lychrel property matters. As you iterate the reverse-and-add process, the numbers get bigger. So if we start with the larger numbers and proceed downwards, then we are more likely to get cache hits. So I tried replacing the line:

for i in range(n):

with

for i in range(n - 1, -1, -1):

and got a further small speedup:

>>> timeit(lambda:problem55_3(10000, 50), number=100)
3.800810826011002

StackExchange Code Review Q#44272, answer score: 6