Consider the following iterative process. Start with a positive integer. If it’s odd, multiply by three and add one. If it’s even, divide it by two. Repeat this process — for example, 5 → 16 → 8 → 4 → 2 → 1. The Collatz Conjecture says that no matter what number you started with, you’ll always eventually return to 1. Proving this is a very important open problem in mathematics.

Write a Hack assembly program to assist in verifying the conjecture experimentally. Your program should follow the process starting with RAM[0] until reaching 1, outputting each number arrived at into memory starting from RAM[32] (so that RAM[0] through RAM[31] stay free for use as variables). For example, if RAM[0] = 5, then the desired output memory state is

RAM[32] = 5, RAM[33] = 16, RAM[34] = 8, RAM[35] = 4, RAM[36] = 2, RAM[37] = 1.

This sort of numerical work was one of the most common applications for early computers.

Hint: For large inputs, even with how slow it is in Hack, it’s much faster to do the division by 2 using a right shift than by using a naive approach. (Imagine how much faster it would be if a right shift were a single instruction!) Modern ISAs usually have instructions for integer multiplication and division... but they also have instructions for left and right shifts, which take fewer cycles! This is worth remembering for if you need to optimise a bit of code that does a lot of multiplication or division by powers of two.