A395424 - OEIS

%I #8 Apr 25 2026 10:50:47

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

%N 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.

%C This sequence is uncomputable.

%C 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))).

%C 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.

%C 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.

%C 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.

%H bbchallenge wiki, <a href="https://wiki.bbchallenge.org/wiki/Fractran">Fractran</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/FRACTRAN">FRACTRAN</a>.

%H Jason Yuen, <a href="https://github.com/int-y1/proofs/tree/master/BBfLean">BBfLean</a>, GitHub repository. This repository contains formal proofs of FRACTRAN programs of size 20, 21, and 22.

%H Jason Yuen, <a href="/A395424/a395424.txt">FRACTRAN programs for a(2)-a(22)</a>.

%H <a href="/index/Br#beaver">Index entries for sequences related to Busy Beaver problem</a>

%e 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.

%e 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.

%Y Cf. A001222, A060843.

%K nonn,hard,more

%O 2,4

%A _Jason Yuen_, Apr 21 2026