Further Optimisation of Project Euler problem 14 (Collatz Sequence)

user_17960293 0
Viewed 96

When I first starting trying the question, my code would take over a minute to even finish running and give me the answer. I have already tried dynamic programming and storing previous numbers so it doesn't have to run the same number multiple times. I have also tried compacting (n3)+1 and n / 2 into a single line with ((n3)+1) but both of these has only managed to cut my code to 10 seconds. Is there anything else I can try to speed up my code?

def Collatz(n):
  dic = {a: 0 for a in range(1,1000000)}
  dic[1] = 0
  dic[2] = 1
  number,length = 1,1
  for i in range(3,n,1):
    z = i
    testlength = 0
    loop = "T"
    while loop == "T":
      if z % 2 == 0:
        z = z / 2
        testlength += 1
      else:
        z = ((z*3)+1) / 2
        testlength += 2
      if z < i:
        testlength += dic[z]
        loop = "F"
    dic[i] = testlength
    if testlength > length:
      print(i,testlength)
      number,length = i,testlength
  return number,length
print(Collatz(1000000))
collatz python
2 Answers

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))
user_54835260

Although the answer from Matt Timmermanns is fast, it is not quite as easy to understand as a recursive function. Here is my attempt that is actually faster for n = 10*million and perhaps easier to understand...

f = 10000000

def collatz(n):
    if n>=collatz.bounds:
        if (n % 4) == 0:
            return collatz(n//4)+2
        if (n % 2) == 0:
            return collatz(n//2)+1
        return collatz((3*n+1)//2)+2
    if collatz.memory[n]>=0:
        return collatz.memory[n]
    if (n % 2) == 0:
        count = collatz(n//2)+1
    else:
        count = collatz((3*n+1)//2)+2
    collatz.memory[n] = count
    return count

collatz.memory = [-1]*f
collatz.memory[1] = 0
collatz.bounds = f

highest = max(collatz(i) for i in range(f//2, f+1))
highest_n = collatz.memory.index(highest)

print(f"collatz({highest_n}) is {highest}")

My results:

$ time /usr/bin/python3 collatz.py 
collatz(8400511) is 685

real    0m9.445s
user    0m9.375s
sys     0m0.060s

Compared to

$ time /usr/bin/python3 mattsCollatz.py 
(8400511, 685)

real    0m10.672s
user    0m10.599s
sys     0m0.066s
user_159605360
Related