FRACTRAN catalogue numbers

$c$	All defined values of $f_c$
0	none
1	$n\rightarrow n$
2	$0\rightarrow 1$
4	$0\rightarrow 2$
8	$1 \rightarrow 2$
16	$2\rightarrow 3$
64	$1\rightarrow 3$
77	$n\rightarrow 0$
128	$0\rightarrow 3$
133	$0\rightarrow 0$
255	$n+1\rightarrow n+1$
256	$3\rightarrow 4$
847	$n\rightarrow 1$
37485	$0\rightarrow 0,n+1\rightarrow n$
2268945	$n\rightarrow n+1$
$2^{2^{b}-2^{a}}$	$a \rightarrow b$
$7\cdot 11^{2^{k}}$	$n\rightarrow k$
${\frac {15}{7}}\cdot 1029^{2^{k-1}}$	$n\rightarrow n+k$
$c_{\pi }$	$n\rightarrow \pi (n)$

Fractran is "a simple universal programming language" devised by John Conway (1987), based on Marvin Minsky's formalized register machines (1961). A Fractran-1 program consists of a list of fractions $\left\{f_{k}\right\}$; computation is carried out using a working number $N$, with initial value a positive integer and successive values given by the product $Nf_{i}$ where $f_i$ is the first fraction in the list for which the product is integral. Computation halts when no such $f_i$ is found. The exponents of the prime factors of $N$ serve as registers, and a fraction ${\frac {p^{a}}{q^{b}}}$ (with $p,q$ prime) serves as the instruction to increment register $p$ by $a$ and decrement register $q$ by $b$.

Conway gives three "free samples" of Fractran programs: PRIMEGAME, which lists the primes, PIGAME, which gives the $n$th digit of $\pi$, and a universal program POLYGAME

${\frac {583}{559}}\,{\frac {629}{551}}\,{\frac {437}{527}}\,{\frac {82}{517}}\,{\frac {615}{329}}\,{\frac {371}{129}}\,{\frac {1}{115}}\,{\frac {53}{86}}\,{\frac {43}{53}}\,{\frac {23}{47}}\,{\frac {341}{46}}$

${\frac {41}{43}}\,{\frac {47}{41}}\,{\frac {29}{37}}\,{\frac {37}{31}}\,{\frac {37}{31}}\,{\frac {299}{29}}\,{\frac {47}{23}}\,{\frac {161}{15}}\,{\frac {527}{19}}\,{\frac {159}{7}}\,{\frac {1}{17}}\,{\frac {1}{13}}\,{\frac {1}{3}}$

for which he proved the following

Theorem. Define $f_{c}(n)=m$ if POLYGAME, when started at $c2^{2^{n}}$, stops at $2^{2^{m}}$, and otherwise leave $f_{c}(n)$ undefined. Then every computable function appears among $f_{0},f_{1},f_{2}\,\cdots$

Conway calls these indices $c$ the "catalogue numbers", and remarks that they "are easily computable for some quite interesting functions". As an example, he gives an integer $c_{\pi }$ such that $f_{c_{\pi }}(n)=\pi (n)$ is the function returning the $n$th digit of $\pi$.

$c_{\pi }=3^{A}\cdot 5^{2^{89\cdot 101!}+2^{90\cdot 101!}}\cdot 17^{101!-1}\cdot 23$

where $A=2^{100!}+\sum _{i=1}^{38}2^{f_{i}\cdot 101^{i}100!}+2^{101^{39}\cdot 100!}$

and the thirty-eight $f_i$'s are the fractions in this version of PIGAME

${\frac {365}{46}}\,{\frac {29}{161}}\,{\frac {79}{575}}\,{\frac {7}{451}}\,{\frac {3159}{413}}\,{\frac {83}{497}}\,{\frac {473}{371}}\,{\frac {638}{355}}\,{\frac {434}{335}}\,{\frac {89}{235}}\,{\frac {17}{209}}\,{\frac {79}{122}}\,{\frac {31}{183}}\,{\frac {41}{115}}\,{\frac {517}{89}}\,{\frac {111}{83}}\,{\frac {305}{79}}$

${\frac {23}{73}}\,{\frac {73}{71}}\,{\frac {61}{67}}\,{\frac {37}{61}}\,{\frac {19}{59}}\,{\frac {89}{57}}\,{\frac {41}{53}}\,{\frac {883}{47}}\,{\frac {53}{43}}\,{\frac {86}{41}}\,{\frac {13}{38}}\,{\frac {23}{37}}\,{\frac {67}{31}}\,{\frac {71}{29}}\,{\frac {83}{19}}\,{\frac {475}{17}}\,{\frac {59}{13}}\,{\frac {41}{3}}\,{\frac {1}{7}}\,{\frac {1}{11}}\,{\frac {1}{1024}}$

which when started at $2^{n}\cdot 89$ stops at $2^{\pi (n)}$.

Sources

[1] J. H. Conway, FRACTRAN: A Simple Universal Computing Language for Arithmetic, in: Open Problems in Communication and Computation (T. M. Cover and B. Gopinath, Eds.), Springer-Verlag: New York 1987, pp. 3-27 (Reprinted in [2])

[2] The Ultimate Challenge: The 3x+1 Problem. Jeffrey C. Lagarias (Ed.). American Mathematical Society 2010.