Run Collatz cycle to one million without processing lag

Admin 1
Viewed 85

I have some Collatz sequence code that finds the greatest length sequence less than or equal to the number the number the user enters. It works fine for relatively smaller numbers. However, I wish to use my code for bigger numbers. Does anyone have any tips to make my code more efficient so it doesn't take minutes for it to run to 1 million?

math dictionary python
1 Answers

Don't ever calculate the same thing twice. You are calculating full collatz sequences that overlap with each other. Once one sequence reduces to a previous one you have calculated you are duplicating work.


collatz_lengths = {1: 1}

def collatz(a):
  if a % 2 == 0:
    return a // 2
  else:  # No need to check a%2 != 0 here
    return 3*a + 1

def find_length(start):
  if start not in collatz_lengths:
    next_number = collatz(start)
    collatz_lengths[start] = 1 + find_length(next_number)
  return collatz_lengths[start]

def longest_length(n):
  max_length = 0
  max_start = 1
  for start in range(1, n + 1):
    collatz_lengths[start] = find_length(start)
    if collatz_lengths[start] > max_length:
      max_length = collatz_lengths[start]
      max_start = start

  return max_start

It only took a few seconds to run

>>> longest_length(1000000)
837799
>>> find_length(837799)
525

And about 20 seconds to run

>>> longest_length(10000000)
8400511
>>> find_length(8400511)
686
user_39838040
Related