CODEWITHSUNDEEP
pythonalgorithmmemoizationcollatz
PoTheBox
PoTheBox

Reputation: 21

Implementing memoization within a Collatz algorithm (Python)

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))

Upvotes: 0

Views: 220

Answers (2)

vorrade -
vorrade -

Reputation: 114

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

Upvotes: 2

sudden_appearance
sudden_appearance

Reputation: 2197

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)

Upvotes: 0

Related Questions