Longest Collatz sequence in Python I came across this problem:


  The following iterative sequence is defined for the set of positive
  integers:

    n → n/2 (n is even)
    n → 3n + 1 (n is odd)

  
  Using the rule above and starting with 13, we generate the following
  sequence:

  13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

  
  It can be seen that this sequence (starting at 13 and finishing at 1)
  contains 10 terms. Although it has not been proved yet (Collatz
  Problem), it is thought that all starting numbers finish at 1.
  
  Which starting number, under one million, produces the longest chain?


and to this I gave this solution:

def number(n):
    ctr = 1
    if n % 2 == 0:
       k = n / 2
       ctr += 1
    else:
       k = 3 * n + 1
       ctr += 1
    while k &gt; 1:
       if k % 2 == 0:
           k /= 2
           ctr += 1
       else:
           k = k * 3 + 1
           ctr += 1
    return ctr

def k(upto):
    largest_number=0
    last_ctr=0
    for num in range(1,upto):
         if number(num)&gt;last_ctr:
            last_ctr=number(num)
            largest_number=num
    return largest_number

print k(999999)


I am new to Python and don't think this is a  good solution to this problem and  maybe its complexity is \$\mathcal{O}(n^2)\$. So what is the best code for this problem if the number is really huge? How do I reduce the complexity?

And yes I read other questions related to this topic but they were not satisfactory answers to this in Python.
The key to solving this problem (and many others) is using memoization: The numbers of the collatz sequence converge in a kind of tree-like structure. Once you have calculated the value of, say collatz(100) on one path, you do not need to calculate it again when you encounter it again on another path.

One way to do this would be to have (a) a cache and (b) a list of all the numbers on the current path. As soon as you encounter a number that is already in the cache, go your path backwards and add all the numbers to the cache.

cache = {1: 1}
def collatz(n):
    path = [n]
    while n not in cache:
        if n % 2:
            n = 3 * n + 1
        else:
            n = n / 2
        path.append(n)
    for i, m in enumerate(reversed(path)):
        cache[m] = cache[n] + i
    return cache[path[0]]


Another, maybe more elegant way would be using recursion and a decorator function. You can define a @memo decorator and use it again and again for all sorts of function you want to apply memoization to. This decorator automatically replaces your function with a version that looks in the cache, first.

def memo(f):
    f.cache = {}
    def _f(*args):
        if args not in f.cache:
            f.cache[args] = f(*args)
        return f.cache[args]
    return _f

@memo
def collatz(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + collatz(n / 2)
    if n % 2 == 1:
        return 1 + collatz(3 * n + 1)


In both cases, call like this and after a few seconds you should get your result.

print(max(range(1, 10**6), key=collatz))