まず、
V =[17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1]
の１４個の有理数をもつ14次元のベクトルを準備しておく。いま、s=2 を、このベクトルの第1
成分から順に、s をかけていくと、
s*V=[34/91,156/85,38/51,46/38,58/33,154/29,190/23,154/19,2/17,22/13,26/11,15,2/7,110]
となり、第12成分ではじめて整数15になる。これを１回目とする。そこで、２回目を、s=15 と置
き直して再びVの第1成分からかけていき、はじめて整数となったところで次のsを決める。
この動きを、{ｎ回目,第ｉ成分ではじめて整数,できた整数ｋ} で追跡してみると、1〜100回目
までの様子は次のことが起きていく。
{ｎ , ｉ , ｋ}={1,12,15},{2,14,825},{3,5,725},{4,6,1925},{5,11,2275},{6,1,425},{7,2,390},{8,10,330},{9,5,290}
{10,6,770},{11,11,910},{12,1,170},{13,2,156},{14,10,132},{15,5,116},{16,6,308},{17,11,364}
{18,1,68},{19,9,4},{20,13,30},{21,13,225},{22,14,12375},{23,5,10875},{24,6,28875},{25,5,25375}
{26,6,67375},{27,11,79625},{28,1,14875},{29,2,13650},{30,1,2550},{31,2,2340},{32,10,1980}
{33,5,1740},{34,6,4620},{35,5,4060},{36,6,10780},{37,11,12740},{38,1,2380},{39,2,2184}
{40,1,408},{41,3,152},{42,4,92},{43,7,380},{44,4,230},{45,7,950},{46,4,575},{47,7,2375}
{48,8,9625},{49,11,11375},{50,1,2125},{51,2,1950},{52,10,1650},{53,5,1450},{54,6,3850}
{55,11,4550},{56,1,850},{57,2,780},{58,10,660},{59,5,580},{60,6,1540},{61,11,1820}
{62,1,340},{63,2,312},{64,10,264},{65,5,232},{66,6,616},{67,11,728},{68,1,136},{69,9,8}
{70,13,60},{71,13,450},{72,13,3375},{73,14,185625},{74,5,163125},{75,6,433125}
{76,5,380625},{77,6,1010625},{78,5,888125},{79,6,2358125},{80,11,2786875}
{81,1,520625},{82,2,477750},{83,1,89250},{84,2,81900},{85,1,15300},{86,2,14040}
{87,10,11880},{88,5,10440},{89,6,27720},{90,5,24360},{91,6,64680},{92,5,56840}
{93,6,150920},{94,11,178360},{95,1,33320},{96,2,30576},{97,1,5712},{98,3,2128}
{99,4,1288},{100,7,5320},････
ここで、第１９回目と６９回目に着目すると、
19回目でできる整数は、4=22 、69回目でできる整数は、8=23
と、２の冪乗に初めてなってみた数は、その２の指数部に素数 2 、3 が現れるという主張な
のである。
従って、100回を越えてさらに先を続けていくと、24 は決して現れず、次の2の冪数は32=25
がどこかで出現するのである。
ステップは長くなるが、必ず ２p (ｐ は素数の小さい順)がこのアルゴリズムから産み出され
ていく。
発案者ジョン・ホートン・コンウェイは、ライフゲームやコンウェイ群やモンスター群、数学的
ゲームなど幅広い独創的アイデアに優れた数学者と昔から大好きな人物でしたが、このよう
な着眼点で素数を産み出せる装置を編み出すことができるなんて、やはり刮目に値する。
どなたか、最初のVは如何にして思いつけるものなのか、説明してもらえれば有り難いです。
らすかるさんからのコメントです。（平成２６年７月１７日付け）
直感ですが、分子・分母に含まれる素因数は29までなので、2^(31^2) が出てきそうな気が
します。
DD++さんからのコメントです。（平成２６年７月１７日付け）
原理は突き止めました。素数判定自体はめちゃくちゃ古典的な原理です。が、なぜこの分
数群で実現できるのかという説明になるとかなり大変……。
ＧＡＩ さんからのコメントです。（平成２６年７月１７日付け）
Kilminster という人物は、W=[3/11,847/45,143/6,7/3,10/91,3/7,36/325,1/2,36/5] と今度
は９個の分数群を使うことで、s=10 でスタートさせ、
10回目：100=102 、46回目：1000=103 、196回目：100000=105 、500回目：10000000=107
･････ （→ 参考：「A183133」）
とやはり １０p (ｐ：prime) を次々と出現させることを発見しています。
任意の ｒ について、s=r から出発させて、ｒp (ｐ：prime) が現れるようにできる分数群は構
成可能ですか？
DD++さんからのコメントです。（平成２６年７月１７日付け）
こんな説明で伝わるでしょうかね。まず前置き。
以下の方法で、素数を全て見つけることができることをご確認ください。
１．赤コインを2枚と青コイン1枚を裏向きに置く
２．赤青どちらかが全部表になるまで1枚ずつ同時に表にする
３A．青が先に全部表を向いたときには青を全て裏返して２．に戻る
３B．赤が先に全部表になったときには青コインを1枚減らし全て裏返して２．に戻る
３C．青赤同時に全部表になったときには各コインの枚数を何らかの方法で出力し、赤コイン
を1枚増やし、青コインをそれより1枚少ない枚数にして全て裏返し２．に戻る
４．.必要なだけ繰り返した後、出力から青コインの枚数が1枚となっているときの赤コインの
枚数を抽出する
つまり、２以上の各自然数に対して、自身を除く最大約数を求めているわけですね。
コンウェイのマシンはこれと同じアルゴリズムで動いています。
[17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1]
この分数群には10種類の素因数が用いられていますが、これが素数であることは素数判定
との直接の関係はなく、どの2つも互いに素な2以上の10個の自然数ならなんでも構いません。
そのうち4組6つ（この場合は11+29,13,17,19+23）は状態切り替え用の値で、残り4つ（2,3,5,7）
は指数を用いた変数格納に使います。
つまり、s=132=2^2×3×11のときは、変数の中身は2,1,0,0で状態は11というように考えるた
めに使うわけです。
例えば、最初の17/91は、状態13かつ7の倍数なら7で割ってから状態17に切り替えると読
むことができます。
さて、状態切り替え用素数は2つ同時に持つことがないので、分数の列をある程度バラして
考えて構いません。
・状態11+29のとき、[29/33, 77/29, 13/11] ・・・ 3を全部7に変えて状態13へ
・状態13のとき、[17/91, 11/13] ・・・ 7の倍数なら、7で割って状態17へ
7の倍数でなければ、状態11へ
・状態17のとき、
[78/85, 19/51, 1/17] ・・・ 5の倍数なら、5で割って2と3をかけて状態13へ
5の倍数でないが3の倍数なら、3で割って状態19へ
5の倍数でも3の倍数でもないなら、状態なしへ行って終了
・状態19+23のとき、[23/38, 95/23, 77/19] ・・・ 2を全部5に変えて、7をかけて状態11へ
・状態なしのとき、[15/2, 1/7, 55/1] ・・・ 2を全部3と5のセットに変えて、7を全部取り除い
て、さらに5をかけて状態11へ
先ほどのコインのアルゴリズムにおいて、
赤いコインの表には「2」で裏には「5」、青いコインの表には「3」で裏には「7」
と書いてあると考えると、多少回りくどいことをしているもののこれらは実は全く同じことをし
ていることが確認できます。
状態なしに戻ってきたとき、数値は17/91をかけた時の影響で、7が1つ減るため、
2^n×7^(nの最大約数-1)となっていて、
ｎ が素数なら、２n・７0 、ｎ が合成数なら、２n・７(1以上)
となります。よって、全ての計算から、2の冪だけ抽出すると、2の素数乗だけが全て並ぶとい
うわけです。
やっていることは単純ですが、よくもまあこんなことを思いつくものです。Kilminsterさんのも
のは詳しく見てませんが、2と5を両方使えることを利用して効率よく構成したのでしょうね。
ＧＡＩ さんからのコメントです。（平成２６年７月１７日付け）
１．について、赤コインも裏向きですか？また、２．について、「１枚ずつ同時」という意味が
どういうことなのか理解しにくいのですが、赤と青を一枚ずつ一緒にひっくり返すと理解して
いいのでしょうか？
この部分をもう少し説明して頂けませんか？
DD++さんからのコメントです。（平成２６年７月１７日付け）
１．２．ついて、GAIさんの仰る通りです。
