FRACTRAN とは

FRACTRANは、数学者John Conwayによって考案されたチューリング完全な難解なプログラミング言語です。 FRACTRANプログラムは、最初の正の整数入力nと共に正の分数の順序付けられたリストです。整数nを次のように更新することによってプログラムが実行されます。
 nfが整数であるリストの最初の小数fについては、nをnfで置き換える。このルールを繰り返すと、nを乗算して停止するまで整数を生成しない。
数学の本では、ジョン・コンウェイとリチャード・ガイは、FRACTRANの素数の数式を与えました:
( 17 91 , 78 85 , 19 51 , 23 38 , 29 33 , 77 29 , 95 23 , 77 19 , 1 17 , 11 13 , 13 11 , 15 14 , 15 2 , 55 1 ) {\displaystyle \left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)}
n = 2から始まるこのFRACTRANプログラムは、以下の整数列を生成します。
(OEIS中の配列A007542)、配列番号2、配列番号15、配列番号825、配列番号725、配列番号1925、配列番号22、
2の後、このシーケンスは2の次の累乗を含みます:
2 2 = 4 , 2 3 = 8 , 2 5 = 32 , 2 7 = 128 , 2 11 = 2048 , 2 13 = 8192 , 2 17 = 131072 , 2 19 = 524288 , {\displaystyle 2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots } (OEISにおける配列A034785)
それは2の主要な力です。