15 de julio de 2012

Project Euler 14


#!/usr/bin/env python

collatz_ht = {} #hashtable
#reverse_collatz_ht = {}

def collatzS(n):
    steps=0
    while n>1:
        if n in collatz_ht:
            return collatz_ht[n]+steps
        if n%2==0:
            n/=2
        else:
            n=3*n+1
        steps+=1
    return steps

def collatz(n):
    if n in collatz_ht:
        return collatz_ht[n]
    else:
        collatz_ht[n]=collatzS(n)
    return collatz_ht[n]

top = 1000000
mx=indx=0
for i in range(2,top):
    if mx<collatz(i):
        mx=collatz(i)
        indx=i
print indx