Problem 14 "Longest Collatz sequence"
Define a sequence of numbers that is repeatedly generated by the following formula for positive integers.
n → n/2 (n is even)\\ n → 3n + 1 (n is odd)Starting from 13, this sequence looks like this:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1There are 10 terms from 13 to 1. This sequence is thought to end up at 1 no matter what number you start with, but that has not yet been proven (Collatz problem).
Now, which of the numbers less than 1 million should start to generate the longest sequence?
Note: May be over 1 million in the middle of the sequence
Python
n = 1000000
seq = range(1, n)
collatz_dict = {1: [1]}
def compute_collatz(i):
if(i not in collatz_dict):
if(i % 2 == 0):
collatz = [i] + compute_collatz(i / 2)
else:
collatz = [i] + compute_collatz(3 * i + 1)
collatz_dict[i] = collatz
return collatz_dict[i]
collatz_lenghs = {}
for i in seq:
collatz = compute_collatz(i)
collatz_lenghs[i] = len(collatz)
max_length = max(collatz_lenghs.values())
max_index = collatz_lenghs.values().index(max_length)
max_length_collatz_key = collatz_lenghs.keys()[max_index]
max_length_collatz = collatz_dict[max_length_collatz_key]
result = max_length_collatz_key
print result
print result == 837799
print max_length
print max_length_collatz[:6]
result
837799
True
525
[837799, 2513398, 1256699, 3770098, 1885049, 5655148]
It's a little late, but I can't think of a good way.
Recommended Posts