Project Euler #14: Longest Collatz Sequence starting point

Question

Problem statement:

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?

NOTE: Once the chain starts the terms are allowed to go above one million. Here is my implementation written in Python, awaiting your feedback.

from time import time
from operator import itemgetter


def collatz_count(n, count={1: 1}):
    """uses cache (count) to speed up the search, returns sequence 
    length for the given number"""
    try:
        return count[n]
    except KeyError:
        if n % 2 == 0:
            count[n] = collatz_count(n / 2) + 1
        else:
            count[n] = collatz_count(n * 3 + 1) + 1
    return count[n]


def run_test():
    """uses the previous function, returns number that generates the 
    largest sequence"""
    time1 = time()
    items = sorted([(x, collatz_count(x)) for x in range(1, 1000000)],
                   key=itemgetter(1), reverse=True)
    maximum = items[0]
    print(f' Starting number: {maximum[0]} \n Sequence length: 
    {maximum[1]} \n '
          f'Calculated in: {time() - time1} seconds.')


if __name__ == '__main__':
    run_test()

Answer 1

Integer Division

In Python, 10 / 2 is equal to 5.0, not 5. Python has the integer division operator (//) which produces an integral value after division, instead of a floating point value. To prevent storing both int and float keys in the count dictionary, you should use:

    count[n] = collatz_count(n // 2) + 1

Cache

Your count cache works nicely. But you don’t have to implement it yourself. Python comes with caching built-in. You just have to request it.

import functools

@functools.lru_cache(None)
def collatz_count(n):
    if n == 1:
        return 1
    elif n % 2 == 0:
        return collatz_count(n // 2) + 1
    else
        return collatz_count(n * 3 + 1) + 1

The first time collatz_count(n) is called with any particular value of n, the function is called and the returned value is memorized in the cache. Any subsequent call with that argument retrieves the value from the cache. (The None value indicates that the cache size is unlimited.)

Sorting to find the maximum

Sorting, in order to find the maximum value, is an \$O(n \log n)\$ in time, and since you need to remember all the values, \$O(n)\$ in space.

There is no need to sort the list; instead, just maintain the largest value encountered so far, and the input which generated that value. This is \$O(n)\$ in time, so much faster, and \$O(1)\$ in space.

And again, it is built-in to Python:

longest_start_number = max(range(1, 1000000), key=collatz_count)
length = collatz_count(longest_start_number)

Docstrings

You are using the docstrings incorrectly.

You shouldn’t say """uses the previous function ... """ in a docstring, because if a user types help(run_test), they will not know what function the previous function is. Even if they type help(module_name) and get help for all the functions in the module, the order the functions get listed in the resulting help output is not necessarily the order of the functions in the module’s source, so again “the previous function” is confusing.

Similarly, saying """uses cache (count) to speed up ...""" is useless, because a user typing help(collatz_count) is expecting to find help on how to use the function, such as what legal values can be given for n, what the return value is, and whether or not the user is expected to pass in a value for count; they don’t need implementation details about how the function was written.

Answer 2

def collatz_count(n, count={1: 1}):
    """uses cache (count) to speed up the search, returns sequence 
    length for the given number"""

Are you sure it speeds it up? It certainly looks completely useless, because neither the looped top call

[(x, collatz_count(x)) for x in range(1, 1000000)]

nor the recursive calls reuse the cache.

Answer 3

time: O(n)

memory: O(1)

collatz_count()

To start, your collatz_count() function could be simpler and easier to read. The recursion in your collatz_count() function is confusing and too long.

Also, do use integer division (//) to cut down on memory (floats take more space than integers).

def collatz_count(n): length = 0 while n != 1: if n & 1: # if n is odd n = 3 * n + 1 else: # if n is even n = n // 2 length += 1 return length

don’t sort, just remember

As another user mentioned, sorting to find the maximum is computationally complex (\$O(n \log n)\$). An alternative is to just remember which starting number gave you the longest path.

One user suggested this:

longest_start_number = max(range(1, 1000000), key=collatz_count) length = collatz_count(longest_start_number)

That works and is better than what you currently have, but it’s more readable and faster to do this:

longest_start_number = 1 length = 1 for i in range(2, 1000000): if collatz_count(i) > length: longest_start_number = i length = collatz_count(i)

print from run_test()

You should generally not print from inside of a function. Instead of returning or printing a custom string, just return the values and leave the printing to the caller:

def run_test():
    # ... code ...
    return longest_start_number, length, time

if __name__ == '__main__':
    longest_start_number, length, time = run_test()
    print(f' Starting number: {longest_start_number} \n Sequence length:  {length} \n '
          f'Calculated in: {time} seconds.'