5
\$\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\$
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
    \$\begingroup\$ thank you so much, this is really helpful. \$\endgroup\$ – emadboctor Jul 15 at 3:58
1
\$\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\$
  • \$\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 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\$ – Peter Taylor Jul 16 at 22:08
1
\$\begingroup\$

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.'
\$\endgroup\$
  • \$\begingroup\$ I don’t know why, but my code simply won’t format properly. Can someone please help me out via an edit? \$\endgroup\$ – Matthew Anderson Jul 15 at 19:10
  • \$\begingroup\$ time taken by collatz_count without recursion using max(range(... 20.505295991897583 seconds. time taken by collatz_count without recursion using for loop... 21.560354948043823 seconds Starting number: 837799 Sequence length: 525 Calculated in: 2.5901660919189453 seconds. \$\endgroup\$ – emadboctor Jul 15 at 20:07
  • \$\begingroup\$ I already a previous version without caching/recursion and it executed in the same time your function executed (almost 20 secs), after caching and use of recursion, it dropped to 2.5 secs, that's why I prefer the other version \$\endgroup\$ – emadboctor Jul 15 at 20:09
  • \$\begingroup\$ @emadboctor, that makes perfect sense. I was actually translating the most efficient alg from Mathematica to Python (Mathematica does t have cache, I’m pretty sure). Thanks for the feedback \$\endgroup\$ – Matthew Anderson Jul 15 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.