0

I stumbled upon a math theory called the Collatz conjecture. Given a non-zero, positive integer, the following two rules are applied:

  1. If it is even, divide n by 2 and repeat.
  2. If it is odd, multiply n by 3, add one to the result, and repeat.

For example, given n=10, the steps would be:

10 > 5 > 16 > 8 > 4 > 2 > 1

After reaching 1, an infinite loop is reached in which it cycles 4, 2, and 1. For my purposes, this is when the steps would end.

This is my solution to compute the steps required for a given range, starting at 1. The following code does not implement a lookup table and results in a linear processing speed:

def threeNplus1(n):
    n = int(n)
    if n == 1:
        return [n]
    elif n % 2 == 0:
        lst = threeNplus1(n / 2)
        lst.insert(0, n)
        return lst
    else:
        lst = threeNplus1(n * 3 + 1)
        lst.insert(0, n)
        return lst


last_number = 1_000
LUT = {}
for n in range(1, last_number+1):
    LUT[n] = threeNplus1(n)

I would like to implement a LUT table to reduce the recursive loops require for extremely large number. For example 10^100 has been solved and 2x10^100 is currently being processed. After one loop, 2x10^100 becomes 10^100 and the solution for this number has already been computed.

I ended up with two codes that are nearly identical, one implements a conditional approach while the other implements an exception approach.

# Conditional approach
def threeNplus1(n, LUT):
    n = int(n)
    if n in LUT.keys():
        return LUT[n]
    elif n == 1:
        return [n]
    elif n % 2 == 0:
        lst = threeNplus1(n / 2, LUT)
        lst.insert(0, n)
        return lst
    else:
        lst = threeNplus1(n * 3 + 1, LUT)
        lst.insert(0, n)
        return lst

and

# Exception approach
def threeNplus1(n, LUT):
    n = int(n)
    try:
        lst = LUT[n]
        return LUT[n]
    except KeyError:    
        if n == 1:
            return [n]
        elif n % 2 == 0:
            lst = threeNplus1(n / 2, LUT)
            lst.insert(0, n)
            return lst
        else:
            lst = threeNplus1(n * 3 + 1, LUT)
            lst.insert(0, n)
            return lst

The implementation for the two codes is:

import copy
last_number = 1_000
LUT = {}
for n in range(1, last_number+1):
    LUT[n] = threeNplus1(n, copy.deepcopy(LUT))

The resulting time complexity is exponential. I was wondering if there are improvements that can be made to reduce the processing time from O(n) or if the implementation of a lookup table within a recursive function is a bad practice due to the increasing size of the variable.

I appreciate any insights or improvements which can be made.

Alex
  • 47
  • 5
  • Why do you need all the deep copies? They're killing your performance for seemingly no gain. You can just use one shared lookup table that's edited in-place. If I had to model this, I would probably create a `Collatz` calculator with: a public `calculate(i)` method, private `threeNplus1` and `divideBy2` methods, and a lookup table stored as an instance variable – Alexander Aug 13 '21 at 22:14
  • The reason your output is slowing is that you're checking the result for every smaller number, even though you wouldn't see all of those values by following the sequence normally. For the Collatz sequence (assuming the conjecture is true!) the LUT can't help you compute the result for a single number (i.e. if you only plan to call the function at top level once) because the entire point is that you won't see any values more than once except for `{4, 2, 1}`. – Karl Knechtel Aug 13 '21 at 22:15
  • That said, you can definitely make use of results from one 'run' of the function to help with another. The general technique is called *memoization* and is explained in detail - along with the built-in standard library solution - at the linked duplicate. – Karl Knechtel Aug 13 '21 at 22:16

0 Answers0