[Question]
  [
[John Horton Conway](https://en.wikipedia.org/wiki/John_Horton_Conway) was a brilliant mathematician. Among his contributions were three Turing-complete esolangs: [Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) ([esolangs wiki](https://esolangs.org/wiki/Game_of_Life)), [FRACTRAN](https://en.wikipedia.org/wiki/FRACTRAN) ([esolangs wiki](https://esolangs.org/wiki/Fractran)), and [Collatz function](https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations) ([esolangs wiki](https://esolangs.org/wiki/Collatz_function)).
Because [we did an extremely amazing job around GoL](https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life), it is time for the challenge with the other two.
## Background
A **FRACTRAN** program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.
A Collatz sequence is defined as the following: given a positive integer \$n\$,
$$
\begin{align}
a\_0 &= n \\
a\_{i+1} &= \begin{cases}
a\_i/2, & \text{if $a\_i$ is even} \\
3a\_i+1, & \text{if $a\_i$ is odd}
\end{cases}
\end{align}
$$
It is conjectured that, for every positive integer \$n\$, the sequence eventually reaches 1.
## Task
Write a FRACTRAN program that takes \$p^n\$ as input (for a prime \$p\$ of your choice) and halts if and only if the Collatz sequence starting at \$n\$ reaches 1.
You may see [Avi F. S.'s COLLATZGAME](https://codegolf.stackexchange.com/a/201483/78410) as an example. Also, [TIO](https://tio.run/##SytKTC4pSsz7DwT/8gtKMvPziv/rZgAA) has [an implementation of FRACTRAN](https://github.com/DennisMitchell/ffi), so you can test your program with it. (Enter the starting number in the Arguments section; it accepts base-exponent form e.g. `2^27` as well as plain integer form.)
The shortest program in terms of **the number of fractions** wins.
  
[Answer]
# ~~9~~ ~~8~~ 7 fractions
$$\frac{5}{4}, \frac{63}{22}, \frac{14}{55}, \frac{66}{35}, \frac{1}{7}, \frac{2}{3}, \frac{44}{5}$$
Takes input as \$3^n\$.
[Try it online!](https://tio.run/##DcjLCcAgEAXAVrYBWdyf3QQkJOBFxVh/XjLHuVc996odcDYKZRHKxu4UweqUuZCwkv0HQA8p75i7jf4gTUW69AM "FRACTRAN – Try It Online")
### How it works
The first transition is
$$3^n \xrightarrow{\frac{2}{3}} 2 \cdot 3^{n - 1},$$
which we will consider the “real” representation of the number \$n\$, because some intermediate control flows will bypass the above transition.
If \$n = 1\$, the program now halts immediately.
If \$n = 2k\$ is even, we have
$$\begin{multline\*}
2 \cdot 3^{2k - 1}
\xrightarrow{\frac{2}{3}}
2^2 \cdot 3^{2k - 2}
\xrightarrow{\frac{5}{4}}
3^{2k - 2} \cdot 5
\xrightarrow{\left(\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{5}{4}\right)^{k - 1}}
5^k
\xrightarrow{\frac{44}{5}}
2^2 \cdot 5^{k - 1} \cdot 11
\\
\xrightarrow{\frac{5}{4}}
5^k \cdot 11
\xrightarrow{\frac{14}{55}}
2 \cdot 5^{k - 1} \cdot 7
\xrightarrow{\left(\frac{66}{35} \cdot \frac{5}{4} \cdot \frac{14}{55}\right)^{k - 1}}
2 \cdot 3^{k - 1} \cdot 7
\xrightarrow{\frac{1}{7}}
2 \cdot 3^{k - 1},
\end{multline\*}$$
which represents \$\frac{n}{2}\$.
If \$n = 2k + 1\$ is odd, we instead have
$$\begin{multline\*}
2 \cdot 3^{2k}
\xrightarrow{\left(\frac{2}{3} \cdot \frac{5}{4} \cdot \frac{2}{3}\right)^k}
2 \cdot 5^k
\xrightarrow{\frac{44}{5}}
2^3 \cdot 5^{k - 1} \cdot 11
\xrightarrow{\frac{5}{4}}
2 \cdot 5^k \cdot 11
\\
\xrightarrow{\frac{63}{22}}
3^2 \cdot 5^k \cdot 7
\xrightarrow{\left(\frac{66}{35} \cdot \frac{63}{22}\right)^k}
3^{3k + 2} \cdot 7
\xrightarrow{\frac{1}{7}}
3^{3k + 2}
\xrightarrow{\frac{2}{3}}
2 \cdot 3^{3k + 1},
\end{multline\*}$$
which represents \$3k + 2 = \frac{3n + 1}{2}\$, which is two steps ahead of \$n\$.
[Answer]
# 9 fractions
```
13/11 22/39 1/13 7/5 320/21 1024/7 3/4 5/6 22/3
```
[Try it online!](https://tio.run/##HcpRCoAgEAXAq@wF5LlvNekyQURBPyrm@dug@Z5r7Mcce3VXg6qQsFUUalKQxRhBFY1MKGJIkrH8yd25sbytz7vVx0Onh5Mf "FRACTRAN – 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](https://codegolf.stackexchange.com/a/203682/20260) 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.
]