How can I improve my code for Euler 14?

Question

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

Here is my code (function to determine collatz chain length

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 that he is weak. Can someone tell me why my code is weak and how I can improve my code in plain English. Keep in mind that I'm new, my programming skills are basic.

Answer 1

Instead of calculating every possible chain from the very beginning to the end, you can save the chain cache and their final length. For example, for a chain

 13 40 20 10 5 16 8 4 2 1 

you could remember the following:

• Collatz chain starting at 13 is 10
• Collatz chain starting at 40 is 9
• Collatz chain starting at 20 is 8

... etc.

Then we can use this stored information to stop the chain calculation as soon as we encounter a number that is already in our cache.

Implementation

Use dictionaries in Python to match start numbers to their chain lengths:

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

Now you just need to adapt your algorithm to use this dictionary (filling it with values, as well as looking at intermediate numbers).

By the way, this can be very well expressed using recursion. The dimensions of the chains that may arise here will not overflow the stack :)

Answer 2

In short, because my English is terrible; -)

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

You can calculate several consecutive iterations at once.

kth iteration of a number ending in k 0 bits:

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

(2k) th iteration 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 for Wikipedia article (in French) ; see also my site (in French) and the tnp1 module in my Python DSPython package.

Combine the following code with the memoization technique 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))