Collatz sequence on a two counter machine

Question

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.

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.

Answer 1

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

Answer 2

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

Answer 3

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
                JMP divisibility    # jump to the beginning of loop

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)
                JMP isDivisible     # jump to beginning of loop

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
                JMP notDivLoop      # jump to beginning of loop

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

Answer 4

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.