Project Euler # 14 "Longest Collatz Sequence" in Python

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 → 1

There 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

Project Euler # 14 "Longest Collatz Sequence" in Python
Functional programming in Python Project Euler 1
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Project Euler # 8 "Maximum Product in Number String" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 12 "High Divisibility Triangular Number" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
Project Euler # 6 "Difference in sum of squares" in Python
Create Python project documentation in Sphinx
Project Euler 11 "Maximum product in grid"
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
Do a non-recursive Euler Tour in Python
I wrote Project Euler 1 in one liner.
Generate the Look-and-say Sequence featured in QuizKnock in Python