Tribute to John Conway: Collatz in FRACTRAN John Horton Conway was a brilliant mathematician. Among his contributions were three Turing-complete esolangs: Game of Life (esolangs wiki), FRACTRAN (esolangs wiki), and Collatz function (esolangs wiki).

Because we did an extremely amazing job around GoL, 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 &amp;= n \\
a_{i+1} &amp;= \begin{cases}
a_i/2,  &amp; \text{if $a_i$ is even} \\
3a_i+1, &amp; \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 as an example. Also, TIO has an implementation of FRACTRAN, 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.
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!

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\$.