# Collatz sequence on a two counter machine

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
otherwise decrement its value
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.

## The challenge

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.

• What program shall we write for the 2CM machine? – FUZxxl Apr 7 '15 at 10:03
• Does your program have to end in HALT or can you also let execution flow off the end? – orlp Apr 7 '15 at 10:03
• Here's a simple interpreter with basic debugging output. – orlp Apr 7 '15 at 12:11
• @LegionMammal978 Doesn't matter for the code size. – FUZxxl Apr 7 '15 at 12:27
• @MarzioDeBiasi Seeing all these comments, let me recommend the sandbox (at least for your next challenge). Writing clear challenges is hard, and even if you think you've sorted it all out, there are often open questions for other users, which can be pointed out in the sandbox and addressed before you post the challenge on main and people start working on it. – Martin Ender Apr 7 '15 at 12:35

# 18 instructions

I was a bit disappointed that I arrived late on scene, as the minimalistic nature of the problem and the language make there (seemingly) only one general approach for a good answer. I got a 19-instruction answer fairly quickly, but I didn't feel like it brought enough to the table to post it. But after much head scratching, my hacky z80 assembly experience came through and I found a way to save an instruction by reusing a block of code for a purpose it wasn't meant for!

# Let N be the previous number in the Collatz sequence.

# Print N, and if N==1, halt.
# X=N, Y=0
Main:           PRINTX          # Print N.
DJZX Done       # X=N-1 (N shouldn't be zero, so this never jumps)
DJZX Done       # If N-1==0, halt. Otherwise, X=N-2.

# Find the parity of N and jump to the proper code to generate the next N.
# X=N-2, Y=0
FindParity:     INCY
DJZX EvenNext   # If N%2==0, go to EvenNext with X=0, Y=N-1.
INCY
DJZX OddNext    # If N%2==1, go to OddNext with X=0, Y=N-1.
JMP FindParity

# Find the next N, given that the previous N is even.
# X=0, Y=N-1
EvenNext:       INCX
DJZY Main       # Y=Y-1 (Y should be odd, so this never jumps)
DJZY Main       # If Y==0, go to Main with X=(Y+1)/2=N/2, Y=0.
JMP EvenNext

# Find the next N, given that the previous N is odd.
# X=0, Y=N-1
OddNext:        INCX
INCX
INCX
DJZY EvenNext   # If Y==0, go to EvenNext with X=(Y+1)*3=N*3, Y=0.
JMP OddNext     # ^ Abuses EvenNext to do the final INCX so X=N*3+1.

# Halt.
Done:           HALT

• I hope my interpreter didn't suck too bad :P Nice solution. – orlp Apr 7 '15 at 17:07
• @orlp Worked like a charm. Thanks. :) – Runer112 Apr 7 '15 at 17:11
• I really like your solution! Very nice abuse of EvenNext :) – Nejc Apr 8 '15 at 8:30

SCORE: 21

Here is my attempt:

main: prints X and jumps to finish (if X==1).

divisibility: makes a distinction if X%2==0 or X%2==1. Also copies X to Y and makes X==0. Jumps to either isDivisible (if X%2==0) or isNotDivisible (if X%2==1).

isDivisible: loop used when Y%2==0. For each decrease of Y by 2, it increases X by 1. When Y==0, jumps to main.

isNotDivisible: used when Y%2==1. It increases X by 1.

notDivLoop: loop used when Y%2==1. For each decrease of Y by 1, it increases X by 3. When Y==0, jumps to main.

finish: halts

main:           PRINTX              # print X
DJZX main           # here X is always >0 and jump never fires (it is just for decreasing)
DJZX finish         # if initially X==1 this jumps to finish
INCX                # establish the previous state of X
INCX
# continue with X>1

divisibility:   DJZX isDivisible    # if X%2==0, then this will fire (when jumping Y=X)
INCY
DJZX isNotDivisible # if X%2==1, this fires (when jumping Y=X)
INCY

isDivisible:    DJZY main           # this jumps to the main loop with X=X/2
DJZY main           # this jump will never fire, because X%2==0
INCX                # for every partition 2 of Y, increase X (making X=Y/2)

isNotDivisible: INCX                # X=0, increase for 1
notDivLoop:     DJZY main           # in each iteration, increase X for 3 (when Y==0, X=3Y+1)
INCX
INCX
INCX

finish:         HALT                # finally halt


Supplied with 3 (using the interpreter supplied by @orlp), the produced result is:

3
10
5
16
8
4
2
1


## 19 instructions

I wrote my own interpreter because I'm fancy like that. Here is my solution for my own interpreter:

MP
XE
XE
HY
XV
XO
JH
WX
VYM
JW
LYM
X
X
OX
X
X
X
JL
EH


And here is what it looks like with syntax compatible to the other interpreter:

# x = n, y = 0
main:    printx
djzx   end
djzx   end

# x = n - 2, y = 0 on fallthrough
half:    incy
djzx   even
djzx   odd
jmp    half

evloop:  incx
# x = 0, y = n / 2  on jump to even
even:    djzy   main
jmp    evloop

oddloop: djzy   main
incx
incx
# x = 0, y = (n + 1) / 2 on jump to even
odd:     incx
incx
incx
incx
jmp    oddloop

end:     halt

• Looks like we found the same solution, you were earlier though :( – orlp Apr 7 '15 at 16:32
• @orlp That happens. – FUZxxl Apr 7 '15 at 16:58

# 19 instructions

found:    PRINTX       # print input/found number
DJZX done    # check if n == 1
DJZX done    # after this point x == n - 2
parity:   INCY         # after this loop y == n // 2
DJZX even
DJZX odd
JMP parity
odd-loop: DJZY found
INCX
INCX
odd:      INCX         # we enter mid-way to compute x = 6y + 4 = 3n + 1
INCX
INCX
INCX
JMP odd-loop
even:     DJZY found   # simply set x = y
INCX
JMP even
done:     HALT


You can run it using my interpreter.

• Duplicate of my answer. – FUZxxl Apr 7 '15 at 17:22
• @FUZxxl That's what I said an hour ago to you :P – orlp Apr 7 '15 at 17:32
• Yes, you did. I wrote this so others realize the equality. – FUZxxl Apr 7 '15 at 17:36