9
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
22
  • \$\begingroup\$ What program shall we write for the 2CM machine? \$\endgroup\$ Commented Apr 7, 2015 at 10:03
  • \$\begingroup\$ Does your program have to end in HALT or can you also let execution flow off the end? \$\endgroup\$ Commented Apr 7, 2015 at 10:03
  • 2
    \$\begingroup\$ Here's a simple interpreter with basic debugging output. \$\endgroup\$ Commented Apr 7, 2015 at 12:11
  • 1
    \$\begingroup\$ @LegionMammal978 Doesn't matter for the code size. \$\endgroup\$ Commented Apr 7, 2015 at 12:27
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Commented Apr 7, 2015 at 12:35

4 Answers 4

Reset to default
12
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I hope my interpreter didn't suck too bad :P Nice solution. \$\endgroup\$ Commented Apr 7, 2015 at 17:07
  • 1
    \$\begingroup\$ @orlp Worked like a charm. Thanks. :) \$\endgroup\$ Commented Apr 7, 2015 at 17:11
  • 1
    \$\begingroup\$ I really like your solution! Very nice abuse of EvenNext :) \$\endgroup\$ Commented Apr 8, 2015 at 8:30
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Looks like we found the same solution, you were earlier though :( \$\endgroup\$ Commented Apr 7, 2015 at 16:32
  • \$\begingroup\$ @orlp That happens. \$\endgroup\$ Commented Apr 7, 2015 at 16:58
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Duplicate of my answer. \$\endgroup\$ Commented Apr 7, 2015 at 17:22
  • \$\begingroup\$ @FUZxxl That's what I said an hour ago to you :P \$\endgroup\$ Commented Apr 7, 2015 at 17:32
  • \$\begingroup\$ Yes, you did. I wrote this so others realize the equality. \$\endgroup\$ Commented Apr 7, 2015 at 17:36

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.