# Project Euler problem 14

Source code available on GitHub.     This is a really interesting problem. Before even thinking about what we’re going to have to do later on, let’s just make a quick function to determine the next number in a Collatz sequence:

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

This quite literally is nothing more than the rule given in the question. Next, we want to generate the whole sequence given a particular starting number:

def CollatzSequence(n):
sequence = [n]
while True:
n = nextCollatz(n)
sequence.append(n)
if n == 1:
break
return sequence

We’re just appending the next term (using the function nextCollatz(n) we just defined) endlessly until we reach 1, and then we return that whole list.

Now we have to find which starting number under a million produces the longest chain. Starting at 999,999 and decreasing the starting number each time rather than the other way round, because it seems plausible that a higher starting number will result in longer sequences on average, we keep calculating the length of each Collatz sequence and if it’s longer than the longest so far, we store both the starting number and the sequence length:

def longestCollatz(cap): # Returns the number below 'cap' which generates the longest Collatz sequence, and its length
longest = 0
for i in range(cap-1,1,-1):
length = len(CollatzSequence(i))
if length > longest:
longest = length
longestAt = i
return longestAt

That’s all there is to it: we print off the answer and we’re done.

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

def CollatzSequence(n):
sequence = [n]
while True:
n = nextCollatz(n)
sequence.append(n)
if n == 1:
break
return sequence

def longestCollatz(cap): # Returns the number below 'cap' which generates the longest Collatz sequence, and its length
longest = 0
for i in range(cap-1,1,-1):
length = len(CollatzSequence(i))
if length > longest:
longest = length
longestAt = i
return longestAt

print(longestCollatz(1000000))