8
1
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.
What program shall we write for the 2CM machine? – FUZxxl – 2015-04-07T10:03:25.420
Does your program have to end in HALT or can you also let execution flow off the end? – orlp – 2015-04-07T10:03:34.220
@orlp: as written in the question (... up to 1 and halts ...) it must HALT – Marzio De Biasi – 2015-04-07T10:07:13.413
@MarzioDeBiasi So a program that just lets the instruction pointer flow off the end of the program is an error? – orlp – 2015-04-07T10:08:55.960
@FUZxxl: as written in the question the 2CM program must "... compute and print the Collatz sequence from n to 1 and HALT ...". For example, when started from X=3 it must print: "3 10 5 16 8 4 2 1" and HALT – Marzio De Biasi – 2015-04-07T10:08:56.683
@MarzioDeBiasi I don't understand your example program either, AFAIK it will just increment once and then halt. – orlp – 2015-04-07T10:13:11.000
@orlp: ouch I missed the jump, sorry – Marzio De Biasi – 2015-04-07T10:15:21.003
@MarzioDeBiasi The quoted text does not appear in the question and I don't find a similar paragraph either. You might want to edit that in. – FUZxxl – 2015-04-07T10:23:43.437
@MarzioDeBiasi Ah! That's what you mean. It's weird that you put it in a block quote. Still, you might want to specify that each number is supposed to be printed out. – FUZxxl – 2015-04-07T10:26:22.750
@FUZxxl: I wrote it in the same paragraph "... and prints ...", furthermore I added an example ?!? – Marzio De Biasi – 2015-04-07T10:27:10.257
@MarzioDeBiasi Okay, sorry, I can't read... – FUZxxl – 2015-04-07T10:29:53.280
Is the input Gödel encoded? a 2CM is only Turing complete when the input is Gödel encoded. – FUZxxl – 2015-04-07T10:31:45.743
@FUZxxl: NO, it is still turing complete with 2 registers, the only hack (for Turing completeness) is that the input/output must be encoded as 2^n but for this question it is irrelevant. You don't need Godel encoding here. – Marzio De Biasi – 2015-04-07T10:32:17.733
what is the initial value of X and Y? (probably you need to get the input in X?) – Nejc – 2015-04-07T11:08:58.147
@Nejc: as written in the question " .... the register X initially contains the starting value n and register Y initially contains 0 ... example ... X=3 ..." ?!?!? – Marzio De Biasi – 2015-04-07T11:33:31.243
@LegionMammal978: ??? The linked (wikipedia) article says "This example shows how to create three more useful instructions: clear, unconditional jump, and copy ...". In every case the instruction set for the question is slightly different (it's more "succinct"). ... mmm ... I'm new to codegolf, but it seems that people here don't pay much attention in what they read :-) – Marzio De Biasi – 2015-04-07T12:00:14.190
2Here's a simple interpreter with basic debugging output. – orlp – 2015-04-07T12:11:24.147
Also, are the instructions 0- or 1-indexed? – LegionMammal978 – 2015-04-07T12:26:59.813
1@LegionMammal978 Doesn't matter for the code size. – FUZxxl – 2015-04-07T12:27:36.003
3
@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 – 2015-04-07T12:35:00.550What is the valid range of input? – FUZxxl – 2015-04-07T15:24:23.443
@FUZxxl: valid inputs: any number greater than 0 on register X (while Y initially contains 0) – Marzio De Biasi – 2015-04-07T15:28:34.893