How to optimise Collatz sequence in python sequence?

Question

The Collatz sequence rules are as follows:

• If n = odd: n = 3n + 1
• If n = even: n = n/2

I am a student with a basic level of python and need to minimise the number of numbers I check to find the longest sequence less than 100. I need to output the starting term of said sequence. Both even numbers and multiples of five can be the answer (if you are looking at answers less than 20 the answer is 18) and am unsure what to check).

Code below works but checks 100 numbers:

highest = 0
highest_num = 0




def Collatz(num, highest, highest_num):
    iterations = 0
    
    while num!=1:
        
        if num%2 == 0:
            num//=2
            
        else:
            num = 3*num + 1
        
        iterations += 1
        
    
    if iterations > highest:
        highest = iterations
        highest_num = i
        print(highest_num)
        
    return highest, highest_num
    

    
    
   
   

for i in range(1, 101, 1):
    result = Collatz(i, highest, highest_num)
    highest = result[0]
    highest_num = result[1]

P.S The answer is 97

Answer 1

You can save result of previously computed numbers is some dict and then use it when you reach some of that numbers. Here is sample code:

cache = {}
max_iter = 0
max_iter_num = 0

def collatz(num):
    global cache
    global max_iter
    global max_iter_num
    
    iterations = 0
    n = num
    numbers = []
    while n > 1:
        numbers.append(n)
        if n%2 == 0:
            n //= 2
        
        else:
            n = 3*n + 1
            
        iterations += 1
        
        if n in cache.keys():
            iterations += cache[n]
            break
        
    for i, n in enumerate(numbers):
        cache[n] = iterations - i
    
    if iterations > max_iter:
        max_iter = iterations
        max_iter_num = num
    

for i in range(1, 101):
    collatz(i)

Time comparision:

• code from question:

626 µs ± 8.08 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

• my code:

67.2 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)