How can I improve my code for euler 14?

Question

I solved Euler problem 14 but the program I used is very slow. I had a look at what the others did and they all came up with elegant solutions. I tried to understand their code without much success.

Here is my code (the function to determine the length of the Collatz chain

def collatz(n):
a=1
while n!=1:
    if n%2==0:
        n=n/2
    else:
        n=3*n+1
    a+=1
return a

Then I used brute force. It is slow and I know it is weak. Could someone tell me why my code is weak and how I can improve my code in plain English. Bear in mind that I am a beginner, my programming skills are basic.

Answer 1

Rather than computing every possible chain from the start to the end, you can keep a cache of chain starts and their resulting length. For example, for the chain

13 40  20  10  5  16  8  4  2  1

you could remember the following:

1. The Collatz chain that starts with 13 has length 10
2. The Collatz chain that starts with 40 has length 9
3. The Collatz chain starting with 20 has length 8

... and so on.

We can then use this saved information to stop computing a chain as soon as we encounter a number which is already in our cache.

Implementation

Use dictionaries in Python to associate starting numbers with their chain length:

chain_sizes = {}
chain_sizes[13] = 10
chain_sizes[40] = 9
chain_sizes[40]   # => 9
20 in chain_sizes # => False

Now you just have to adapt your algorithm to make use of this dictionary (filling it with values as well as looking up intermediate numbers).

By the way, this can be expressed very nicely using recursion. The chain sizes that can occur here will not overflow the stack :)

Answer 2

Briefly, because my English is horrible ;-)

Forall n >= 1, C(n) = n/2     if n even,
                      3*n + 1 if n odd

It is possible to calculate several consecutive iterates at once.

kth iterate of a number ending in k 0 bits:

C^k(a*2^k) = a

(2k)th iterate of a number ending in k 1 bits:

C^(2k)(a*2^k + 2^k - 1) = a*3^k + 3^k - 1 = (a + 1)*3^k - 1

Cf. formula on Wikipédia article (in French); see also my website (in French), and Module tnp1 in my Python package DSPython.

Combine the following code with the technique of memoization explained by Niklas B :

#!/usr/bin/env python
# -*- coding: latin-1 -*-
from __future__ import division  # Python 3 style in Python 2
from __future__ import print_function  # Python 3 style in Python 2


def C(n):
    """Pre: n: int >= 1
    Result: int >= 1"""
    return (n//2 if n%2 == 0
            else n*3 + 1)


def Ck(n, k):
    """Pre: n: int >= 1
         k: int >= 0
    Result: int >= 1"""
    while k > 0:
        while (n%2 == 0) and k:  # n even
            n //= 2
            k -= 1

        if (n == 1) and k:
            n = 4
            k -= 1
        else:
            nb = 0
            while (n > 1) and n%2 and (k > 1):  # n odd != 1
                n //= 2
                nb += 1
                k -= 2

            if n%2 and (k == 1):
                n = (n + 1)*(3**(nb + 1)) - 2
                k -= 1
            elif nb:
                n = (n + 1)*(3**nb) - 1

    return n


def C_length(n):
    """Pre: n: int >= 1
    Result: int >= 1"""
    l = 1

    while n > 1:
        while (n > 1) and (n%2 == 0):  # n even
            n //= 2
            l += 1

        nb = 0
        while (n > 1) and n%2:  # n odd != 1
            n //= 2
            nb += 1
            l += 2
        if nb:
            n = (n + 1)*(3**nb) - 1

    return l


if __name__ == '__main__':
    for n in range(1, 51):
        print(n, ': length =', C_length(n))