Project Euler 14 asks: Which starting number, under one million, produces the longest Collatz sequence?
I've been trying to optimize this solution to execute in less then 1s. Agenda for first 50 eulers. Currently it executes in 1,2s for me, so I guess that I want it to be 20% faster. Any tips or other methods?
from time import time
def rec_col(n, cache):
if n in cache:
return cache[n]
x = (rec_col(n//2, cache) if n % 2 == 0 else rec_col(3*n+1, cache))+1
cache[n] = x
return x
def main():
start = time()
highest = 0
ans = 1
cache = {1: 1}
for i in range(1, 10**6):
temp = rec_col(i, cache)
if temp > highest:
ans = i
highest = temp
print("{0}\nTime {1:.4f} s".format(ans, time() - start))
if __name__ == '__main__':
main()
This has the same preformance:
def rec_col(n, cache):
cache[n] = (rec_col(n//2, cache) if n % 2 == 0 else rec_col(3*n+1, cache)) + 1 \
if n not in cache else cache[n]
return cache[n]