The Collatz sequence starting from a positive integer n is defined in this way:
- if n is even then divide it by 2 (
n' = n / 2)
- if n is odd then multiply it by 3 and add 1 (
n' = 3n + 1)
Repeat the above iteration until n reaches 1.
It is not known (it's a major unsolved problem in number-theory) if the sequence will eventually reach the number 1, regardless of which positive integer is chosen initially.
A Two Counter Machine (2CM) is a machine equipped with two registers that can hold a non-negative integer value and can be programmed with the following instruction set:
INCX increase the value of register X INCY increase the value of register Y JMP n jump to instruction n DJZX n if register X is zero jump to instruction n, otherwise decrement its value DJZY n if register Y is zero jump to instruction n, otherwise decrement its value HALT halt (and accept) PRINTX print the content of register X
A 2CM program is simply a sequence of instructions, for example the following program simply copies the content of register X to register Y:
cp: DJZX end INCY JMP cp end: HALT
Note that a 2CM is Turing Complete (i.e. it can compute every computable function with a suitable input encoding, but it is irrelevant here). Also note that the instruction set is a little bit different from the one in the Wikipedia article.
Write the shortest 2CM program, that computes and prints the collatz sequence up to 1 and halts (the register X initially contains the starting value
n and register Y initially contains 0). Note that the length of a 2CM program is the number of instructions used (not the length of the text).
For example, when started from X=3 it must print:
3 10 5 16 8 4 2 1 and HALT.
So you can use your favourite language to build a 2CM simulator/interpreter, but the final (shortest) code that you put in the answer must be in the 2CM language.