9 fractions
13/11 22/39 1/13 7/5 320/21 1024/7 3/4 5/6 22/3
Try it online! Input is a power of 2.
It's probably easier to think about FRACTRAN code in terms of the powers of the primes in each fraction. I list these below for the code, with positive exponents coming from numerators and negative values from denominators, omitting 0's to reduce clutter. Thinking of programs as lists of vectors and the current value as a vector, FRACTRAN repeatedly modifies the value by adding the first-listed row such this results in no negatives entries.
2 3 5 7 11 13
----------------
-1 +1
+1 -1 +1 -1
-1
-1 +1
+6 -1 +1 -1
+10 -1
-2 +1
-1 -1 +1
+1 -1 +1
I suspect this solution is similar to Anders Kaseorg's earlier 9-byte solution, who has already explained how his now-more-golfed answer works in detail. So, I'll instead explain a useful conceptual idea in my code.
Switcher gadget
I'll talk about a control flow gadget that I'll call a switcher that my code heavily relies on. You can see two copies of it, one in columns 3 and 4, and another in columns 5 and 6. It looks like this:
-1 +1
B +1 -1
b -1
A
a +1
Here, A
, a
, B
, and a
are some FRACTRAN operations, taking up multiple columns. A switcher alternates between two things:
- Repeat
A
as long as it's legal, then do a
once.
- Repeat
B
as long as it's legal, then do b
once.
The first row -1 +1
doesn't do any code operation is just used for control flow.
Here's how a switcher it might look like operating. The first column shows the operation performed, and the other two columns showing the value of those variables used for control flow, which are always 0 or 1.
A 0 0
A 0 0
A 0 0
a 1 0
0 1
B 1 0
0 1
B 1 0
0 1
B 1 0
0 1
b 0 0
A 0 0
A 0 0
...
What is it good for?
So, why do we want a switcher? Well, without a gadget like this, it's hard to keep FRACTRAN focused on a task. Say we want to alternate between doing A
repeatedly and doing B
repeatedly. FRACTRAN prioritizes the one that's listed first, so if we list A
then B
, then when doing B
, FRACTRAN will keep jumping back to A
when it can. Of course, the other order means we just have the same problem with it jumping back to B
.
For example, consider this simple program made of two operations:
A = [-2, +1]
B = [+1, -1]
Starting with [2*n, 0]
, these operations almost work to product [n, 0]
but not quite. First, A
is applies as long as possible, adding [-2, +1]
until we arrive at[0, n]
. For example, with n=3
, this goes:
[6, 0]
add A: [4, 1]
add A: [2, 2]
add A: [0, 3]
Now we have [0, n]
and want to get [n, 0]
. To move n
back to the first entry, we want to to keep adding B = [+1, -1]
. Since we can't do A
at first, the code indeed switches to B
, but then things go wrong:
[0, 3]
add B: [1, 2]
add B: [2, 1]
add A: [0, 2]
Because doing B
twice made A
applicable again, it never finishes applying B
and so doesn't get to [n, 0]
.
A switcher lets us fix exactly this by keeping the program on task with B
, making it alternates between A
-mode and B
-mode until each respective task is complete and can be done no further. It also let us run additional one-time operations a
and b
when switching modes.
The Collatz code
This operation of halving is exactly what the Collatz code does on even values. If we ignore the third and fourth columns (which are for odd values) and their rows, we get:
code switcher
-1 +1
(B) +1 -1 +1 -1
(b) -1
(A) -2 +1
(a) +1 -1 +1
This is exactly a switcher (in columns 3 and 4) applies to the operations in the first two columns. These are the halving operations A = [-2, +1], B = [+1, -1]
described before. A detail is that we also have b = A
to make the transition from B
work out by doing A
an additional time in advance.
Similarly, columns 3 and 4 are a switcher for the operation used for odd values. To take [n,0] -> [3*n+1,0]
for odd n
, we use:
A = [-2, +1]
a = [-1, -1]
B = [+6, -1]
b = [+10, 0]
Note that making B
be [+6, -1]
rather than [+1, -1]
as for the even case means that we end up with a result about 6 times as big, so 3*n
rather than n/2
. The a
and b
work out to give the +1
in 3*n+1
while serving other useful purposes. Specifically, they make the code go into the odd switcher rather than the even switcher when the first entry is odd, as well as make the program terminate when the Collatz sequence reaches 1.
The odd code might be a bit simpler producing (3*n+1)/2
, that is pre-doing an addition halving step, which is always what follows because 3*n+1
is even for odd n
. But, I think that this would just make the numerical entries in the rows smaller rather than cutting a row (fraction), which is what counts for scoring.
1/2
for inputs of form 3^n be a correct solution if the collatz conjecture were proven to be true? \$\endgroup\$