7
\$\begingroup\$

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_lychrel(number):
            candidates.append(number)

    time = datetime.now() - start_time # To get the time of the calculation

    print('In {} were found {} lychrel candidates'.format(time, len(candidates)))
    print(' '.join(map(str, candidates)), 'are candidates.')
    suml = input('Press ENTER to close ')

On my PC (with Intel Atom 2GHz), I got it with .4 seconds. Could you offer suggestions on making it run faster?

\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

Hints

  1. According to the example in the problem description, 349 is not a Lychrel number. As a hint for speeding things up, I'd like to point out that the example computation might also tell you something about, say, the number 1292.

    What I'm trying to say is that when you evaluate 1292, you will be performing part of the same computation that you already did with 349. The same applies to the reversed forms of each number, but there's a catch: the reversal is not symmetric when trailing zeros are present. 210 reversed is 12, but 12 reversed is 21.

  2. A single reverse-add operation typically maps multiple numbers to the same number. If you figure out how that works, you can reduce the number of cases you need to consider.

Changes suggested by hint 1

  • To be able to take timings with timeit, I first rearranged your top-level code to a function. I also changed the ranges to 50 and 10000, for reasons explained in Gareth's answer.

    def e55():
        candidates = []
        for number in range(10000):
            if is_lychrel(number):
                candidates.append(number)
        return len(candidates)
    

    This runs in 158 ms on my computer:

    $ python3 -m timeit -s "from e55_op import e55" "e55()" 
    10 loops, best of 3: 158 msec per loop    
    
  • The main function could be written more concisely. This one is marginally slower at 161 ms:

    def e55():
        return sum(1 for number in range(10000) if is_lychrel(number))
    
  • Now to the performance optimization. I want to avoid following the same sequence of iteration more than once. First, I'll extract the loop from is_lychrel into a recursive function. This in itself does not make it run faster, but neither does it slow it down.

    def check(number, depth):
        ''' Returns True if 'number' is neither a palindrome
        nor becomes one in 'depth' iterations of reverse-add.'''
        rev = reverse(number)
        return number != rev and (not depth or check(number + rev, depth-1))
    
    def is_lychrel(number):
        ''' Returns True if 'number' is a lychrel candidate,
            but works only with numbers from 1 to 10000 '''
        return check(number + reverse(number), 49) 
    
  • The speedup comes from making the recursive function cache its return values in a dictionary. I'll also eliminate the is_lychrel function as it is called from only one place.

The complete code is below and runs in 36.5 ms. I also timed Gareth's proposal: 54.8 ms.

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 check(number, depth, cache):
    ''' Returns True if 'number' is neither a palindrome
        nor becomes one in 'depth' iterations of reverse-add.'''
    if number not in cache:
        rev = reverse(number)
        cache[number] = (number != rev 
            and (not depth or check(number + rev, depth-1, cache)))
    return cache[number]

def e55():
    cache = {}
    return sum(1 for number in range(10000) 
               if check(number + reverse(number), 49, cache))

Notes:

  • I'm resetting the cache inside e55 because timeit runs the function multiple times. Each iteration has to be able to start from the same state.
  • Calling check with depth=49 causes 50 iterations to be evaluated, because it starts from an already reverse-added number.

Hint 2: math

Let's consider all 4-digit numbers. Labeling the digits abcd we can represent the number as

a*1000 + b*100 + c*10 + d

Reverse-add results in

(a+d)*1000 + (b+c)*100 + (c+b)*10 + (d+a)
= (a+d)*1001 + (b+c)*110

As a ranges from 1 to 9 and the other digits from 0 to 9, (a+d) can take values from 1 to 18 and (b+c) from 0 to 18. Thus there are 18*19 = 342 possible values for the expression (a+d)*1001 + (b+c)*110. That gives an opportunity to speed up the program if we make it loop over the 342 sums instead of the 9000 4-digit numbers. There is the extra complication that we need to calculate how many numbers map to each reverse-add result, but that is not very complicated.

The 3-, 2- and 1-digit cases can be analyzed in the same way.

Hint 2: implementation

I'm using collections.Counter to determine how many ways there are to add two numbers for each sum. I've inlined the reverse function because it is called from only one place.

This code runs in 4.64 ms, which is a 34X speedup from the original.

from collections import Counter

def check(number, depth, cache):
    ''' Returns True if 'number' is neither a palindrome
        nor becomes one in 'depth' iterations of reverse-add.'''
    if number not in cache:
        rev = int(str(number)[::-1])
        cache[number] = (number != rev 
            and (not depth or check(number + rev, depth-1, cache)))
    return cache[number]

def cases():
    ''' Yields numbers that can result from reverse-adding numbers
        below 10000, and the frequency of each'''
    freqs00_99 = Counter(i % 10 + i // 10 for i in range(100))
    freqs10_99 = Counter(i % 10 + i // 10 for i in range(10,100))

    for i in range(10):
        yield 2*i, 1        # from one digit
    for i, f_outer in freqs10_99.items():
        yield 11*i, f_outer # from two digits
        for j in range(10):
            yield 101*i + 20*j, f_outer  # from three digits
        for j, f_inner in freqs00_99.items():
            yield 1001*i + 110*j, f_outer*f_inner   # from four digits

def e55():
    cache = {}
    return sum(freq for i, freq in cases() if check(i, 49, cache))
\$\endgroup\$
1
  • \$\begingroup\$ I just cant see to get a simple approach using this way to think, because doing that is going to require more conditions and probably is going to be the same running time or even worse. What do you think ? Do you have an idea to improve this ? \$\endgroup\$ Mar 16, 2014 at 1:47
6
\$\begingroup\$

1. Comments on your code

  1. 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.

  2. 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?

  3. 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.

  4. 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
    

2. Speeding it up

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

  2. 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
    
  3. 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
    
  4. 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
    
\$\endgroup\$
2
  • \$\begingroup\$ I interpret "below ten thousand" as < 10000, not ≤ 10000. (But that's splitting hairs about something that makes no difference in this case.) \$\endgroup\$ Apr 13, 2014 at 2:38
  • \$\begingroup\$ I interpret that phrase in the same way as you do. Did I make a mistake? \$\endgroup\$ Apr 13, 2014 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.