Conway's prime machine

最近読んだ、とある量子情報理論の教科書に紹介されていたネタですが、

• 14個の分数　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　を用意
• N=2から出発して、「上の14個の分数のうち、Nに掛けると整数になる最初の数字をNに掛けて、その結果を新しいNとする」という操作を繰り返す
• 途中でNが2の累乗となったら、そのNを出力（して引き続き上の手順を繰り返す）

とすると、4（=2の2乗）、8（=2の3乗）、32（=2の5乗）、といった具合に「2の素数乗」の形の数が（そして、そのような形の数だけが）順番に出力されるのだそうです。
実際の計算例は長いので最後に。

これはConway's FRACTRANなどといった名前で呼ばれる「プログラミング言語」によるプログラムの一例だそうですが、こんな方法で素数の列が得られるなんて、初見だとかなりびっくりしますよね。少なくとも私はしました。
証明は例えばこちらで見られます*1ので、よろしければどうぞ。

証明を追ってみて、何となく、「ミクロコスモス」のように持駒変換やら馬鋸やらが絡み合って盤面が少しずつ進んでいく長編詰将棋に似た雰囲気だなぁ、と私は思いました。
というより、あの手の長編詰将棋がむしろプログラミング的な雰囲気を持っている、と言った方が適切なのかもしれませんが。

どの程度有名なのかわかりませんが、話のネタにでも。

以下、実際の計算例です。
実際に計算してみると、まず、N=2に掛けて整数になる最初のリスト中の数は最後から二番目の15/2なので、Nを2×15/2=15に変更。
次は、15倍して整数になる最初の数は一番最後の55/1なので、Nを15×55/1=3×5×5×11に変更。
次は、掛けて整数となる最初の数が29/33なので、Nを3×5×5×11×29/33=5×5×29に変更。
といった具合に進めていくと、以下Nが5×5×7×11、5×5×7×13、5×5×17、2×3×5×13、2×3×5×11、2×5×29、2×5×7×11、2×5×7×13、2×5×17、2×2×3×13、2×2×3×11、2×2×29、2×2×7×11、2×2×7×13、2×2×17、2×2と変遷していき、最初の出力「2の2乗」が得られます。

*1:英語の上に少々誤記がありますが