I approached the problem as follows:
import functools
def euler_014(max_=1000000):
longest = max_len = None
for n in range(1, max_):
length = len_collatz(n)
if max_len is None or length > max_len:
max_len, longest = length, n
return longest
def memoize(f):
cache = {}
@functools.wraps(f)
def func(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return func
@memoize
def len_collatz(n):
if n == 1:
return 1
if n % 2:
n = (n * 3) + 1
else:
n //= 2
return 1 + len_collatz(n)
Here memoize
makes things more efficient by storing previous results for len_collatz
, len_collatz
tells you the length of the sequence from n
to 1
(without actually generating a list of the whole sequence) and euler_014
simply has to keep track of the longest length and the associated value of n
. Note that it doesn't keep all of the results - just the length of the longest series so far and the value of n
that produced that sequence.