# Longest Collatz Sequence

```# Longest Collatz sequence
#
# The following iterative sequence is defined for the set of positive integers:
#
#   n -> n / 2 (n is even)
#   n -> 3n + 1 (n is odd)
#
# Using the rule above and starting with 13, we generate the following sequence:
#
#   13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
#
# It can be seen that this sequence (starting at 13 and finishing at 1) contains
# 10 terms. Although it has not been proved yet (Collatz Problem), it is thought
# that all starting numbers finish at 1.
#
# Which starting number, under one million, produces the longest chain?
#
# https://projecteuler.net/problem=14

def collatz(seq_lst, n):
# append starting value
seq_lst.append(int(n))
while n > 1:
# even
if n % 2 == 0:
n = n / 2
seq_lst.append(int(n))
# odd
else:
n = 3 * n + 1
seq_lst.append(int(n))

return seq_lst

assert collatz([], 13) == [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

# solution (slow)

MAX_RANGE = 1000000

longest = (0, 0)

for n in range(MAX_RANGE):
seq = collatz([], n)
if len(seq) > longest:
longest = (n, len(seq))

print(longest)
# 837799
```