def collatz_next (n):
    if (n % 2)==0: # even
        return n/2
    else: # odd
        return 3*n+1


def seq_len(start, calculated_chains):
    #print ("seq_len(start=%d...)" % start)
    total=0
    n=start
    while True:
        if n==1:
            rt=total+1 # including starting
            #print ("if start at %d, %d steps to 1 is required" % (start, rt))
            calculated_chains[start]=rt
            return rt
        if n in calculated_chains:
            #print ("got %d in calculated_chains" % n)
            rt=calculated_chains[n]+total+1
            calculated_chains[start]=rt
            return rt
        n=collatz_next(n)
        total=total+1

calculated_chains={}
#lens={}
max_seq_len=0
for i in range (1,1000000):
#for i in range (1,1000):
#for i in range (1,40):
    #print ("testing i=%d" % i)
    s=seq_len(i, calculated_chains)
    if s>max_seq_len:
        max_seq_len=s
        final_n=i
        print ("max_seq_len is now %d, final_n=%d" % (s, final_n))