Implementing memoization within a Collatz algorithm (Python)

Question

I am trying to perform a Collatz algorithm on the following code. It works fine when I use a range of 1-10 etc... However, if the range is for example 1-500,000 it's too slow and won't ever show me the output of the longest sequence.

numberArray = []

s=int(1)
f=int(10)

def collatz(n):
    global count
    if n == 1:
        count += 1
        numberArray.append(count)
        return True
    elif (n % 2) == 0:
        count += 1
        collatz(n/2)
    else:
        count += 1
        collatz(3*n+1)
        
for i in range (s, f+1):
  count = 0
  ourNumber = i
  collatz(i)

print(max(numberArray))

Answer 1

Stef means something like this, which uses a dictionary to memorise the values that have already been counted:

s = 1
f = 10000000

def collatz(n):
    if n in collatz.memory:
        return collatz.memory[n]
    if (n % 2) == 0:
        count = collatz(n//2)+1
    else:
        count = collatz((3*n+1)//2)+2
    collatz.memory[n] = count
    return count

collatz.memory = {1:0}

highest = max(collatz(i) for i in range(s, f+1))
highest_n = max(collatz.memory, key=collatz.memory.get)

print(f"collatz({highest_n}) is {highest}")

Output: collatz(8400511) is 685

Answer 2

Use lru_cache decorator. Its function to memorize (cache) the returned value of function called with specific argument.

Also read how to write clean code in python

The next code solves your problem

from functools import lru_cache

number_array = []

s = 1
f = 500000


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


for i in range(s, f + 1):
    number_array.append(collatz(i))

print(number_array)