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 (rational numbers), 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}}$. The numerator and denominator of any rational number fraction do not share any prime factors (they are in reduced form). 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}}\}$. As with Turing machines, we will write $s\stackrel{N}{\to }t$ if $s\to s_1\to \cdots \to s_{N-1}\to t$ (s goes to t after N steps) and $s{\to }^{*}t$ or $s{\to }^{+}t$ if $s\stackrel{N}{\to }t$ for some N≥0 or N≥1 (respectively). We say that a program has runtime N (or halts in N steps) starting in state s if $s\stackrel{N}{\to }t$ and computation halts on t.

Let $\mathrm{\Omega }(n)$ be the total number of prime factors of a positive integer n. In other words, $\mathrm{\Omega }(2^{a_0}{3}^{a_1}\cdots p_n^{a_n})=\sum _{k=0}^n{a}_n$. 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.

Vector Representation

Fractran programs are not easy to interpret, in fact it may be completely unclear at first that they can perform any computation at all. One of the key insights is to represent all numbers (states and rules) in their prime factorization form. For example, we can use a vector $[a_0,a_1,\dots ,a_{n-1}]\in {\mathbb{\mathbb{Z}}}^n$ to represent the number $2^{a_0}{3}^{a_1}\cdots p_{n-1}^{a_{n-1}}$.

Let the vector representation (for a sufficiently large n) for a state $a=2^{a_0}{3}^{a_1}\cdots p_{n-1}^{a_{n-1}}$ be $v(a)=[a_0,a_1,\dots ,a_{n-1}]\in {\mathbb{\mathbb{N}}}^n$ and the vector representation for a rule $\frac{a}{b}$ be $v\left(\frac{a}{b}\right)=v(a)-v(b)\in {\mathbb{\mathbb{Z}}}^n$ (Note that this is just an extension of the original definition extended to allow negative $a_i$).

Now, rule q applies to state s iff $v(s)+v(q)\in {\mathbb{\mathbb{N}}}^n$ (all components of the vector are ≥0) and if $s\to t$ then $v(t)=v(s)+v(q)$. So the fractran multiplication model is completely equivalent to the vector adding model. For presentation, we will represent a fractran program with a matrix where each row is the vector representation for a rule.

For example, the BBf(15) champion ([1/45, 4/5, 3/2, 25/3]) in vector representation would be:

$$\left[\begin{array}{ccc}0& -2& -1\\ 2& 0& -1\\ -1& 1& 0\\ 0& -1& 2\end{array}\right]$$

In this representation, it becomes much easier to reason about fractran programs and describe general rules. It is also very easy to calculate the size of a rule or program in vector representation. It is the sum of absolute values of all elements in the matrix + number of rules (number of rows).

Champions

The table of champions is split into two pieces: the first for small champions (up to BBf(14)) which all share the same relatively simple behavior (sequential programs) is collapsed by default; the second for champions BBf(15) and beyond which have more complex and varied behavior.

All small champions as well as the first few larger ones were discovered and proven maximal by Jason Yuen (@-d) in their initial enumeration on 1 Nov 2025.

Small Champions

n	BBf(n)	Example Champion	Vector Representation
2	1	[1/2]	$\left[\begin{array}{c}-1\end{array}\right]$
3	1	[3/2]	$\left[\begin{array}{cc}-1& 1\end{array}\right]$
4	1	[9/2]	$\left[\begin{array}{cc}-1& 2\end{array}\right]$
5	2	[3/2, 1/3]	$\left[\begin{array}{cc}-1& 1\\ 0& -1\end{array}\right]$
6	3	[9/2, 1/3]	$\left[\begin{array}{cc}-1& 2\\ 0& -1\end{array}\right]$
7	4	[27/2, 1/3]	$\left[\begin{array}{cc}-1& 3\\ 0& -1\end{array}\right]$
8	5	[81/2, 1/3]	$\left[\begin{array}{cc}-1& 4\\ 0& -1\end{array}\right]$
9	6	[243/2, 1/3]	$\left[\begin{array}{cc}-1& 5\\ 0& -1\end{array}\right]$
10	7	[729/2, 1/3]	$\left[\begin{array}{cc}-1& 6\\ 0& -1\end{array}\right]$
11	10	[27/2, 25/3, 1/5]	$\left[\begin{array}{ccc}-1& 3& 0\\ 0& -1& 2\\ 0& 0& -1\end{array}\right]$
12	13	[81/2, 25/3, 1/5]	$\left[\begin{array}{ccc}-1& 4& 0\\ 0& -1& 2\\ 0& 0& -1\end{array}\right]$
13	17	[81/2, 125/3, 1/5]	$\left[\begin{array}{ccc}-1& 4& 0\\ 0& -1& 3\\ 0& 0& -1\end{array}\right]$
14	21	[243/2, 125/3, 1/5]	$\left[\begin{array}{ccc}-1& 5& 0\\ 0& -1& 3\\ 0& 0& -1\end{array}\right]$

n	BBf(n)	Example Champion	Vector Representation	Champion Found	Holdouts Proven
15	28	[1/45, 4/5, 3/2, 25/3]	$\left[\begin{array}{ccc}0& -2& -1\\ 2& 0& -1\\ -1& 1& 0\\ 0& -1& 2\end{array}\right]$	Jason Yuen (@-d) 1 Nov 2025	Jason Yuen (@-d) 1 Nov 2025
16	53	[1/45, 4/5, 3/2, 125/3]	$\left[\begin{array}{ccc}0& -2& -1\\ 2& 0& -1\\ -1& 1& 0\\ 0& -1& 3\end{array}\right]$	Jason Yuen (@-d) 1 Nov 2025	Jason Yuen (@-d) 1 Nov 2025
17	107	[5/6, 49/2, 3/5, 40/7]	$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& 2\\ 0& 1& -1& 0\\ 3& 0& 1& -1\end{array}\right]$	Jason Yuen (@-d) 1 Nov 2025	Daniel Yuan (@dyuan01) 3 Nov 2025
18	211	[5/6, 49/2, 3/5, 80/7]	$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& 2\\ 0& 1& -1& 0\\ 4& 0& 1& -1\end{array}\right]$	Jason Yuen (@-d) 4 Nov 2025	Jason Yuen (@-d) 8 Nov 2025
19	370	[5/6, 49/2, 3/5, 160/7]	$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& 2\\ 0& 1& -1& 0\\ 5& 0& 1& -1\end{array}\right]$	@creeperman7002 5 Nov 2025	Decider: Daniel Yuan (@dyuan01) 13 Nov 2025 3 Holdouts: Racheline & Shawn Ligocki
20	≥ 746	[7/15, 22/3, 6/77, 5/2, 9/5]	$\left[\begin{array}{ccccc}& -1& -1& +1& \\ +1& -1& & & +1\\ +1& +1& & -1& -1\\ -1& & +1& & \\ & +2& -1& & \end{array}\right]$	Jason Yuen (@-d) 13 Nov 2025

Behavior of Champions

Sequential programs

All champions up to BBf(14) have very simple behavior. They are all of the form: $[\frac{3^{a_1}}{2},\frac{5^{a_2}}{3},...\frac{p_n^{a_k}}{p_{k-1}},\frac{1}{p_k}]$ or in vector representation (limited to k=4):

$$\left[\begin{array}{ccccc}-1& a_1& 0& 0& 0\\ 0& -1& a_2& 0& 0\\ 0& 0& -1& a_3& 0\\ 0& 0& 0& -1& a_4\\ 0& 0& 0& 0& -1\end{array}\right]$$

These champions repeatedly apply the rules in sequence, never going back to a previous rule. They apply the first rule until they've exhausted all 2s, then the second rule until they've exhausted all 3s, etc. They have a runtime of $1+a_1+a_1{a}_2+a_1{a}_2{a}_3+\cdots =\sum _{i=0}^k\prod _{j=1}^i{a}_j$ and size $2k+2+\sum _{i=1}^k{a}_i$. This grows linearly for k=1 (BBf(5) to BBf(10)) and quadratically for k=2 (BBf(11) to BBf(14)). Letting k grow with the size, the maximum runtime grows exponentially in the program size.

BBf(17) Family

The BBf(17) to BBf(19) champions are members of a family of programs (parameterized by $m,n\ge 0$)

$$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& n\\ 0& 1& -1& 0\\ m& 0& 1& -1\end{array}\right]$$

which have size $m+n+12$

This family obeys the following rules:

1. $[1,0,0,0]\stackrel{1}{\to }[0,0,0,n]$
2. if d≥1 and b≤m:$$[0,b,0,d]\stackrel{m+b+2}{\to }[0,b+1,0,d-1+n(m-b)]$$
3. if d≥1 and b≥m:$$[0,b,0,d]\stackrel{2m+2}{\to }[0,b+1,0,d-1]$$
4. if d=0: [0,b,0,d] has halted

and furthermore these rules are applied in order since b is always increasing (and d is eventually decreasing). Combining these together we get runtime:$$1+n(m+1)(m(m+1)+2)-\frac{m(m+1)}{2}$$

The optimal choices for n,m for various program sizes are:

Size	n	m	Runtime
16	1	3	51
17	2	3	107
18	2	4	211
19	2	5	370
20	2	6	596
21	3	6	904

BBf(20)

The BBf(20) champion (running 746 steps):

$$\left[\begin{array}{ccccc}& -1& -1& +1& \\ +1& -1& & & +1\\ +1& +1& & -1& -1\\ -1& & +1& & \\ & +2& -1& & \end{array}\right]$$

This program implements a Collatz-like iteration. Let $C(n)=[0,0,n,2,0]$, then:

$$\begin{array}{lcl}[1,0,0,0,0]& \stackrel{49}{\to }& C(2)\\ C(3k)& \stackrel{3k}{\to }& \text{halt}\\ C(3k+1)& \stackrel{11k+22}{\to }& C(4k+3)\\ C(3k+2)& \stackrel{11k+22}{\to }& C(4k+4)\\ \end{array}$$

which follows the reasonably "lucky" trajectory:

$$C(2)\to C(4)\to C(7)\to C(11)\to C(16)\to C(23)\to C(32)\to C(44)\to C(60)\to \text{halt}$$

Cryptids

No fractran Cryptids have been found yet via enumeration, but some have been constructed by hand.

Hydra

A size 29 program that simulates Hydra rules: [507/22, 26/33, 245/2, 5/21, 1/3, 11/13, 22/5] and in vector form (here the 0s have been omitted to avoid clutter):

$$\left[\begin{array}{cccccc}-1& +1& & & -1& +2\\ +1& -1& & & -1& +1\\ -1& & +1& +2& & \\ & -1& +1& -1& & \\ & -1& & & & \\ & & & & +1& -1\\ +1& & -1& & +1& \end{array}\right]$$

The intended interpretation is that if we let $S(h,w)=[1,0,0,w,h-3,0]$ then it follows the following rules:

$$\begin{array}{lcl}[1,0,\dots ]& =& S(3,0)\\ S(2k,0)& {\to }^{*}& \text{halt}\\ S(2k,w+1)& {\to }^{*}& S(3k,w)\\ S(2k+1,w)& {\to }^{*}& S(3k+1,w+2)\\ \end{array}$$

BMO1

A size 49 program which simulates BMO1 rules:

$$\left[\begin{array}{cccccccccc}-1& & & +1& & & & & & +1\\ & -1& +1& & & & & -1& -1& +2\\ & -1& & +1& & & & -1& & +1\\ & -1& & & +1& & & +1& -1& \\ & & & -1& & +1& & & +2& -1\\ & +1& & -1& & & & +1& & \\ & & & & -1& & +1& +1& & -1\\ & +1& & & -1& & & & +1& \\ & +1& -1& & & & & & & \\ & & & +1& & -1& & & & \\ & & & & +1& & -1& & & \\ \end{array}\right]$$

Let $A(a,b)=[0,1,0,0,0,0,0,a,b,0]$, then it follows the rules:

$$\begin{array}{lcl}[1,0,\dots ]& {\to }^{*}& A(1,2)\\ A(a,b)& {\to }^{*}& A(a-b,4b+2)& \text{if }a>b\\ A(a,b)& {\to }^{*}& A(2a+1,b-a)& \text{if }a<b\\ A(a,b)& {\to }^{*}& \text{Halt}& \text{if }a=b\\ \end{array}$$