Further Optimisation of Project Euler problem 14 (Collatz Sequence)

Solution 1:

When you calculate the sequence for one input, you find out the sequence length for all the intermediate values. It helps to remember all of these in the dictionary so you never have to calculate a sequence twice of any number < n.

I also started at (n-1)//2, since there's no point testing any number x if 2x is going to be tested later, because 2x will certainly have a longer sequence:

def Collatz(n):
    dic = [-1]*n
    dic[1] = 0
    bestlen = 0
    bestval = 1
    q=[]
    for i in range((n-1)//2,n,1):
        q.clear()
        z = i
        while z >= n or dic[z] < 0:
            q.append(z)
            if z % 2 == 0:
                z = z//2
            else:
                z = z*3+1
        testlen = len(q)+dic[z]
        if testlen > bestlen:
            bestlen = testlen
            bestval = i
            print (bestval, bestlen)
        for j in range(0,len(q)):
            z = q[j]
            if z < n:
                dic[z] = testlen-j
    return bestval, bestlen

print(Collatz(1000000))