Collatz Conjecture Efficient max step length finding algorithm with memoization

tnpo.py

# Collatz conjecture:
# https://en.wikipedia.org/wiki/Collatz_conjecture#Iterating_on_all_integers

import sys

# s,f=sys.stdin.readline().split()
# s=int(s)
# f=int(f)
s = 1
f = 1000000
#s and f are now integers containing the start and finish values

cache = {1: 1}

def TNPO(n):
  offset = 1  # sequence offset (i.e. the amount of steps after the last element of the sequence)
  sequence = []  # sequence of numbers produced by the algorithm

  while n != 1:
    if n in cache.keys():
        offset = cache[n]
        break

    sequence.append(n)

    if n % 2 == 1:  # odd
      n = 3 * n + 1
    else:  # even
      n = n / 2


  count = len(sequence) + offset  # add the remaining steps

  while len(sequence) > 0:
    cache[sequence.pop(0)] = len(sequence) + offset

  return count


# entry point here
maxLen = 1
for n in range(s, f + 1):
  if n not in cache.keys():  # if the number has already been in the sequence of another then it won't be longer
    l = TNPO(n)
    if l > maxLen:
      maxLen = l

#print(cache)
print(maxLen)