Skip to content

Instantly share code, notes, and snippets.

@phsteve
Last active December 22, 2015 09:48
Show Gist options
  • Save phsteve/6454576 to your computer and use it in GitHub Desktop.
Save phsteve/6454576 to your computer and use it in GitHub Desktop.
Project Euler Problem 14
#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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment