6
\$\begingroup\$

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()
\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ thank you so much, this is really helpful. \$\endgroup\$
    – user203258
    Jul 15, 2019 at 3:58
2
\$\begingroup\$
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.

\$\endgroup\$
2
  • \$\begingroup\$ Yes, it does speed it up. See the "Valid uses for mutable defaults" section in Default Parameter Values in Python. The dictionary created in the parameter count={1: 1} is a global object that gets stored in collatz_count.__defaults__, and each time n is not found in the count dictionary, the except KeyError: block will store the computed value there. It is more of a side effect of using a mutable object as a parameter default, which normally results in disaster, but in this case actually is useful. @functools.lru_cache is better. \$\endgroup\$
    – AJNeufeld
    Jul 16, 2019 at 19:59
  • 1
    \$\begingroup\$ Ugh. That's the kind of trick which is "clever" enough to need commenting every single time it's used. \$\endgroup\$ Jul 16, 2019 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.