Project Euler Problem 14

p14.py

#The Collatz sequence is defined by the following rules on the set of positive numbers:

# n -> n/2 if n is even
# n -> 3n + 1 if n is odd

#Starting with 13, the sequence proceeds:
# 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1

#Which starting number, under 1,000,000 produces the longest chain?

def next_collatz(n):
    if n % 2 == 0:
        return n / 2
    else:
        return 3 * n + 1

#MEMOIZE THIS

memo = {}
# #memo is a mapping of a number to its Collatz sequence, e.g. {5 : [5, 16, 8, 4, 2, 1]}
# #this could get huge

def memo_len_collatz(n):
    #rather than creating a cache of numbers mapped to their whole sequences,
    #make a cache that maps numbers to the length of their sequences
    #memo can be a list where the value of memo[index] corresponds to the len of the sequence

    #build it up from 1

    

def memo_collatz(n):
    if n in memo.keys():
        return memo[n]
    elif n == 1:
        return [1]
    else:
        memo[n] = [n] + memo_collatz(next_collatz(n))
        return memo[n]

def brute_collatz(n):
    seq = [n]
    next = next_collatz(n)
    if n != 1:
        return seq + brute_collatz(next)
    else:
        return [1]

#print brute_collatz(5)
#print memo_collatz(6)
#print memo
def longest_collatz(k):
    longest = (1, 1)
    for i in range(1, k):
        length = len(memo_collatz(i))
        if length > longest[1]:
            longest = (i, length)
    return "The longest collatz sequence starts at %d with length %d" %longest
print longest_collatz(1000000)