The Collatz Conjecture, also known as the 3n + 1 conjecture or the hailstone sequence, is a conjecture in Mathematics. As the name suggests, it is a conjecture - an opinion or conclusion formed based on incomplete information - named after Lothar Collatz, who first proposed it in 1937. This conjecture states that if you take any positive integer and repeatedly perform the following operations:
   * If the number is even, divide it by 2.
   * If the number is odd, multiply it by 3 and add 1.
You will eventually reach the number 1, no matter which positive integer you start with.

In this post, I will discuss how I would implement an algorithm to return the number of steps it takes for a given positive integer to get to the number 1 according to the Collatz Conjecture. I’ll take an iterative approach. As postulated by the conjecture, we assume every positive integer input will eventually reach the number 1. Since this is still an open problem, there are different opinions on the time complexity so we won’t delve into that in this post. Using the operations stated above, let’s take a first shot at it.

def steps_to_one(n: int) -> int:
    if not type(n) == int:
        raise TypeError("Input must be of type int")

    if not n >= 1: 
        raise ValueError("Input value must be greater or equal to 1")

    no_of_steps = 0

    while n != 1:
      if n % 2 == 0:
        n = n / 2
      else:
        n = (3 * n) + 1
        
      no_of_steps += 1
        
    return no_of_steps

Done, that was straightforward, right? A quick review of the code; first, there is a type-check to ensure the input, n, is an integer, followed by a value-check to ensure n is greater or equal to 1. Next, a counter for the number of steps taken is initialized to 0 and while n is not 1, perform an even number check on n using the mudulo operator and divide n by 2 if it is an even number else multiply it by 3 and add 1. Increment the number of steps by 1 after. Continue the procedure till n has a value of 1 then exit out of the while loop and return the number of steps.

Let’s assume this function is to be invoked multiple times with different positive integers of increasing magnitude; can we alter steps_to_one for a better runtime? Right, we can add an element of memoization in the form of a reference map to keep track of ‘seen’ numbers with their no_of_steps value and then leverage that for the next input so we don’t have to go through every single step in the iteration cycle. Let’s take a shot at that.

class Collatz:
    def __init__(self) -> None:
        self.memo = {}

    def steps_to_one(self, n: int) -> int:
        if not type(n) == int:
            raise TypeError("Input value must be of type int")

        if not n >= 1:
            raise ValueError("Input value must be greater or equal to 1")

        no_of_steps = 0

        while n != 1:
            if n in self.memo:
                return self.memo[n] + no_of_steps

            if n % 2 == 0:
                n = n / 2
            else:
                n = (3 * n) + 1

            no_of_steps += 1

        if not n in self.memo:
            self.memo[n] = no_of_steps
        return no_of_steps

Some modifications have been made to the code snippet. We now have a class Collatz with an init method (constructor) which initializes the reference map as an empty Python dictionary. Just after the while condition, the reference map, memo, is checked for the input n, if n exists in memo, we return the known no_of_steps for n at that instance plus the accrued no_of_steps so far to get the actual no_of_steps value for the original input, n. If not, n goes through the iteration cycle and finally n together with it’s no_of_steps are inserted into memo.

This implementation adds a layer of memoization/temporary caching hence if an object of the class is created and used to invoke steps_to_one with different positive integers (in increasing order of magnitude), it will have a relatively better performance as compared to the earlier implementation.
This is how I would implement the Collatz Conjecture in Python.