# Optimizing Code for Project Euler Problem 14

For Project Euler problem 14 I wrote code that runs for longer than a minute to give the answer. After I studied about memoization, I wrote this code which runs for nearly 10 seconds on Cpython and nearly 3 seconds on PyPy. Can anyone suggest some optimization tips?

import time
d={}
c=0
def main():
global c
t=time.time()
for x in range(2,1000000):
c=0
do(x,x)
k=max(d.values())
for a,b in d.items():
if b==k:
print(a,b)
break

print(time.time()-t)

def do(num,rnum):
global d
global c
c+=1
try:
c+=d[num]-1
d[rnum]=c
return
except:
if num==1:
d[rnum]=c
return
if num%2==0:
num=num/2
do(num,rnum)
else:
num=3*num+1
do(num,rnum)

if __name__ == '__main__':
main()

-

I think you're over complicating your solution, my approach would be something along these lines:

def recursive_collatz(n):
if n in collatz_map:
return collatz_map[n]
if n % 2 == 0:
x = 1 + recursive_collatz(int(n/2))
else:
x = 1 + recursive_collatz(int(3*n+1))
collatz_map[n] = x
return x


Basically define a memoization map (collatz_map), initialized to {1:1}, and use it to save each calculated value, if it's been seen before, simply return.

Then you just have to iterate from 1 to 1000000 and store two values, the largest Collatz value you've seen so far, and the number that gave you that value.

Something like:

largest_so_far = 1
highest = 0
for i in range(1,1000000):
temp = recursive_collatz(i)
if temp > largest_so_far:
highest = i
largest_so_far = temp


Using this approach I got:

Problem 14's answer is: 837799. Took 1.70620799065 seconds to calculate.

-