How to write cache function or equivalent in Python?

Question

Question from Daily Coding Problem 210 as reproduced below:

A Collatz sequence in mathematics can be defined as follows. Starting with any positive integer:

if n is even, the next number in the sequence is n / 2
if n is odd, the next number in the sequence is 3n + 1

It is conjectured that every such sequence eventually reaches the number 1. Test this conjecture.

Bonus: What input n <= 1000000 gives the longest sequence?

My code (note that it is incomplete):

def collatz(n):
    sequenceLength = 0
    while (n>=1):
        if (n==1):
            break # solution is found
        elif (n%2==0):
            n = n/2
            sequenceLength += 1
        else:
            n = 3*n+1
            sequenceLength += 1
    return(sequenceLength)

def longest_seq(limit):
    result = []
    for i in range(1, limit+1):
        result += [collatz(i)]
    print(result)
    return max(result)

Question: In this case, I need to test the conjecture that I will always reach "1" for all positive integers. However, my code above assumes this which means I could potentially run an infinite loop.

What is a good/elegant method to test the conjecture? I was thinking something along the lines of a cache/array to see if values of "n" are repeated at the beginning of the while loop. If so, it suggests an infinite loop. However, I am a bit stuck on the syntax part and not clear on the examples I've seen so far. I just need a way to: - Add things to a cache/equivalent - Check whether something exists within the cache/equivalent (and this either gives me a proper return or an elegant invalid response that I can use, without crashing my program)

Much thanks.

Answer 1

Since every time you encounter a specific number n_i you will do the same operation, you know that if you encounter a number that you have already seen then you will loop infinitely.

One way to solve this is to save your sequence. Then you can verify at each step that you haven't already encountered the number. Here is what it could look like :

def collatz(n):
    sequence = []
    while (n>=1):
        if n in sequence:
            break
        else:
            sequence.append(n)
            if (n==1):
                break # solution is found
            elif (n%2==0):
                n = n/2
            else:
                n = 3*n+1
    return(sequence)

Note : You can use a set instead of an array if you want the code to run faster since arrays have longer lookup time (credit to @tobias_k). But you will lose the exact order of your sequence.

Answer 2

There is a built-in decorator for this purpose in python: lru_cache. But first you should use a recursive function to benefit from decorators.

from functools import lru_cache

@lru_cache()
def collatz(n):
    sequenceLength = 0
    if n == 1:
        return n
    elif n % 2 == 0:
        return 1 + collatz(n // 2)
    else:  # n % 2 == 1:
        return 1 + collatz(3 * n + 1)

You can check here how it works and modify it to do what you want: https://docs.python.org/3/library/functools.html

You want to check if an input has already been seen before, you can define your own decorator:

def deco(f):
    cache = {}
    @wraps(f)
    def wrapper(*args, **kwargs):
        if 'r' in kwargs and kwargs['r']:  # reset the cache when first called
            cache.clear()
        try:                                                                                                    
            res = cache[args]  
            # We have already seen these parameters !
            print('cache hit', *args)
            if res is None:
                raise KeyError
        except KeyError:
            cache[args] = None  # temporary store a value here
            res = f(*args)
            cache[args] = res  # final value stored
        return res

    return wrapper

You just need to change your definition of collatz:

@deco
def collatz(n, /):  # force positional argument here
    # ... (same code here)

And call it with a reset:

collatz(10, r=True)
>>> 7

But as tobias said, this code should never trigger for collatz function

Answer 3

Recursion + caching:

cache = {1:0}
def collatz(n):
    if n in cache:
       return cache[n]
    else:
       if n%2==0:
          m = n//2
       else:
          m = 3*n+1
       res = collatz(m) + 1
       cache[n] = res
       return res


def longest_seq(limit):
    result = []
    for i in range(1, limit+1):
        result += [collatz(i)]
    return max(result)

Then running:

r =  longest_seq(1000000)
#524

Find the value corresponding to the max:

[x for x,y in cache.items() if y==r]
#[837799]