Fractran

Fractran (originally styled FRACTRAN) is an esoteric Turing complete model of computation invented by John Conway in 1987. In this model a program is simply a finite list of fractions, the program state is an integer. For more details see https://en.wikipedia.org/wiki/FRACTRAN

BB_fractran(n) or BBf(n) is the Busy Beaver function for Fractran programs.

Definition

A fractran program is a list of rational numbers $[q_0,q_1,...q_{k-1}]$called rules and a fractran state is an integer $s\in \mathbb{\mathbb{Z}}$. We say that a rule $q_i$ applies to state $s$ if $s\cdot q_i\in \mathbb{\mathbb{Z}}$. If no rule applies, we say that the computation has halted otherwise we apply the first applicable rule at each step. In that case we say $s\to t$ and $t=s\cdot q_i$ and $i=\min \{i:s\cdot q_i\in \mathbb{\mathbb{Z}}\}$. We say that a program has runtime N (or halts in N steps) starting in state s if $s\to s_1\to \cdots \to s_N$ and no rule applies to $s_N$.

Let $\mathrm{\Omega }(n)$ be the total number of prime factors of a positive integer n. In other words $\mathrm{\Omega }(1)=0$ and $\mathrm{\Omega }(pn)=\mathrm{\Omega }(n)$ for any prime number p. Then given a rule $\frac{a}{b}$ we say that $\text{size}\left(\frac{a}{b}\right)=\mathrm{\Omega }(a)+\mathrm{\Omega }(b)$. And the size of a fractran program $[q_0,q_1,...q_{k-1}]$ is $k+\sum _{i=0}^{k-1}\text{size}(q_i)$.

BB_fractran(n) or BBf(n) is the maximum runtime starting in state 2 for all halting fractran programs of size n. It is a non-computable function akin to the Busy Beaver Functions since Fractran is Turing Complete.

Champions

n	BBf(n)	Example Champion(s)
1	0	[1/1]
2	1	[1/2]
3	1	[3/2]
4	1	[9/2]
5	2	[3/2, 1/3]
6	3	[9/2, 1/3]
7	4	[27/2, 1/3]
8	5	[81/2, 1/3]
9	6	[243/2, 1/3]
10	7	[729/2, 1/3]
11	10	[27/2, 25/3, 1/5]
12	13	[81/2, 25/3, 1/5]
13	17	[81/2, 125/3, 1/5]
14	21	[243/2, 125/3, 1/5]
15	28	[1/45, 4/5, 3/2, 25/3]
16	53	[1/45, 4/5, 3/2, 125/3]
17	107	[5/6, 49/2, 3/5, 40/7]
18	211	[5/6, 49/2, 3/5, 80/7]
19	≳ 370	[5/6, 49/2, 3/5, 160/7]