A395424 Busy Beaver problem for FRACTRAN: a(n) is the maximal number of steps that a FRACTRAN program of size n can make on the integer 2 before eventually halting.

1, 1, 1, 2, 3, 4, 5, 6, 7, 10, 13, 17, 21, 28, 53, 107, 211, 370, 746, 31957632

Offset

2,4

Comments

This sequence is uncomputable.

The size of a FRACTRAN program [f_1, f_2, ..., f_k] is defined as Sum_{i=1..k} (1 + A001222(numerator(f_i)) + A001222(denominator(f_i))).

For a(n), it is enough to consider FRACTRAN programs with at most n fractions. Furthermore, it is enough to consider numerators and denominators that use the first n primes in their prime factorization.

a(22) >= 114613926700260640237968442298168949531348819453104518623702295 because the program [1/12, 9/10, 14/3, 11/2, 5/7, 3/11] makes this many steps before eventually halting.

Conjecture: These 3 programs of size 22 are non-halting: [1/15, 27/77, 49/3, 10/49, 33/2], [1/15, 49/3, 27/77, 10/49, 33/2], and [27/35, 1/33, 25/3, 22/25, 21/2]. A proof would require solving a Collatz-like problem. For more details, see "Fenrir" in the bbchallenge wiki.

Links

Table of n, a(n) for n=2..21.

bbchallenge wiki, Fractran.

Wikipedia, FRACTRAN.

Jason Yuen, BBfLean, GitHub repository. This repository contains formal proofs of FRACTRAN programs of size 20, 21, and 22.

Jason Yuen, FRACTRAN programs for a(2)-a(22).

Index entries for sequences related to Busy Beaver problem

Example

For n = 2, the FRACTRAN program [1/2] has size (1+0+1) = 2 and this program makes 1 step before halting: 2 -> 1. This is maximal among all programs of size 2, so a(2) = 1.
For n = 11, the FRACTRAN program [27/2, 25/3, 1/5] has size (1+3+1)+(1+2+1)+(1+0+1) = 11 and this program makes 10 steps before halting: 2 -> 27 -> 225 -> 1875 -> 15625 -> 3125 -> 625 -> 125 -> 25 -> 5 -> 1. This is maximal among all programs of size 11, so a(11) = 10.

Crossrefs

Cf. A001222, A060843.

Sequence in context: A308019 A008814 A005140 * A176486 A017845 A211698

Adjacent sequences: A395420 A395421 A395422 * A395425 A395426 A395427

Keyword

nonn,hard,more

Author

Jason Yuen, Apr 21 2026

Status

approved