Euler Project 14 Longest Collatz Sequence [closed]

Question

I have been working through the euler project and I have created the following code for Problem 14, which asks which starting number, under 1 million, produces the longest Collatz Sequence chain.

It takes a good minute to process. Can I make it faster?

class Collatz:

    def __init__(self):
        self.c = 1

    def if_even(self, n):
        return int(n / 2)

    def if_odd(self, n):
        return int(n * 3 + 1)

    def decide(self, n):
        if (n & 1) == 0:
            return self.if_even(n)
        elif (n & 1) == 1:
            return self.if_odd(n)

    def iter_nums(self, n):
        if n == 1:
            return n
        self.c += 1
        n = self.decide(n)    
        self.iter_nums(n)

largest = 0

# col = Collatz()
# col.iter_nums(13)

# print(col.c)


for i in range(1000000, -1, -1):
    col = Collatz()
    col.iter_nums(i)
    if col.c > largest:
        largest = i

print(largest)

Answer 1

This problem really lends itself to dynamic programming. How many times to you really need to re-calculate the sequence starting at 10, which never changes? Remember that value and reuse it.

I wrote this like:

from functools import lru_cache

@lru_cache(None)
def coll(num):
    if num == 1:
        return 1

    if num % 2:
        return 1 + coll(num * 3 + 1)

    return 1 + coll(num / 2)

longest = 0
for i in range(1, 1_000_001):
    this = coll(i)
    if this > longest:
        print(i, this)
        longest = this

Without taking any special steps to optimize this, just that memoization dropped the runtime to 2.8s on my laptop.

Answer 2

Useless calls to int

When n is an integer:

• n * 3 + 1 is an integer as well, you don't need to call int

• int(n / 2) can also be computed using the "floored quotient" with the // operator.

You don't need a class

I highly recommend watching Jack Diederich's talk called "Stop Writing Classes". Classes are a great tool but they are not always needed, sometimes the problem can be solved with simple tools like functions.

In your case, the whole class can be restricted to a simple function, shorter, clearer, more efficient, easier to use.

def get_collatz_length(n):
    if n == 1:
        return 1
    return 1 + get_collatz_length((3 * n + 1) if (n & 1) else n // 2)

You don't need recursion

Once again, recursion can be a great way to write a concise solution for a given problem. However, in Python, it is sometimes best to avoid it: there is no tail-recursion optimisation and the call stack has a fairly limited size.

You could write something like:

def get_collatz_length_loop(n):
    l = 1
    while n != 1:
        n = (3 * n + 1) if (n & 1) else n // 2
        l += 1
    return l

To be continued: memoization

Is bitwise optimisation relevant?

Answer 3

A function which computes all the numbers in the Collatz sequence, and then returns just the length of the sequence, but not the actual numbers, seems like over optimization and/or specialization. If one then wants the numbers in the Collatz sequence, you need to write effectively the same function again.

Instead, one can create a generator for Collatz sequences:

def collatz(n):
    yield n
    while n > 1:
        n =  n * 3 + 1  if  n % 2  else  n // 2
        yield n

Then, if you want a collatz sequence, you can easily get it:

>>> print(list(collatz(13)))
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

If you want the length of the sequence, you can quickly count the number of elements the generator emits without creating the actual list:

>>> sum(1 for _ in collatz(13))
10

Determining the length of the longest sequence for all starting numbers up to 1 million still takes under 30 seconds on my laptop, even with the overhead of the generator and yield statements.

>>> max(sum(1 for _ in collatz(i)) for i in range(1000001))
525

Determining the starting number for the sequence whose length is 525 is left as an exercise to the student.