308 : 脅威の素数生成オートマトン

プログラミング言語Fractranで書かれたプログラムは, 分数のリストから構成される.

Fractranの仮想マシンの内部状態は正の整数であり, あるシード値が初期にセットされる. Fractranの各反復では, リストのうち, 状態の整数との積が整数となる初めの分数が状態の整数に掛けられる.

例えば,John Horton Conwayが書いた素数生成を行うFractranのプログラムの一つは, 次の14の分数から構成される:

$\displaystyle \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}{2}, \frac{1}{7}, \frac{55}{1}$

シードの整数 2 から始めると, プログラムの反復計算を行うと次の数列が得られる: 15, 825, 725, 1925, 2275, 425, ..., 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

この数列に現れる 2 のべき乗は$2^2, 2^3, 2^5, \dots$ である. この数列のすべての 2 のべき乗は素数の指数を持ち, かつすべての素数は 2 のべき乗の指数として, 適切な順序で現れることが示せる.

上のFractranのプログラムを用いてProject EulerのProblem 7（10001 番目の素数を求めよ）を解くと, プログラムが$2^{(10001番目の素数)}$を生成するまでに何回の反復が必要になるか.