Lermerの篩機械

先日のことだが, Mountain ViewにあるComputer History Museumに行ってきた. 思い込みの深い多くの計算機に対面できた. ただ残念ながらLehmerの初代の自転車のチェーンによる篩機械はドイツに出張中とかで, 見られなかった. これについて私は以前こう書いた. (bit 1997年7月号)

『「先日のことだが, ...」計算整数論者でカリフォルニア大学バークレイ校(以下UCB)教授だったDerrick Henry Lehmer(以下Dick)は昔のエピソードでもこう語り始めるのを好んだ. 私もひとつ真似をしよう.

先日のこと, Dickは集めてきた自転車のチェーンの部品でチェーンの輪を19個作った. それぞれの輪のリンク数は67までの素数だが, 13までの素数に対する輪は小さ過ぎるので64, 27, 25, 49, 22, 26とした. これをそれぞれ同軸に固定した10枚歯のスプロケットに掛け, 回転数をカウンターで数えながら軸をモーターで回転した. 輪は零の位置(または素数の倍数の位置)にピンを立てた時, カウンターが大きな整数Nになるまで軸を回転し, 停止時にどのピンも真上になければNには67以下の素因数はないわけだ.

また探すべき数が, いろいろな素数での法がいくつかという条件さえわかれば, その位置にピンを立て, ピンと接点, リレー, モーターを組合せ, 条件を満たす数が見つかった時点で回転を停止する機構も工夫した.

軸は300rpmで回転したので, 1日に432万個(=10×300×60×24)の整数を調べることができた. だが, この篩計算機を作った目的のMersenne数, 2²⁵⁷-1の素数性を調べるは$10⁷⁰年かかるらしい. さよう, Dickがこの篩を試作したのは, 彼がUCBの学部学生であった1926年のことである. この機械の複製はボストンのコンピュータミュージアムにあるが, 展示はしていないらしい. 』

Computer History Museumは1990年代にBostonからCaliforniaへ移動している. インターネットで探すとcomputer history museumに写真は見つかった.



どういう問題を解くか. Lehmerのような整数論者は高尚な問題を解くだろうが, 簡単な例はChinese Remainder Theoremのようなものである. つまり3で割れば1余り, 5で割れば2余り, 7で割れば3余る数はなにか.

3での剰余がp, 5での剰余がq, 7での剰余がrなら70p+21q+15r mod 105が解で, 今の70+42+45=157, 157 mod 105 = 52 となる. この程度なら篩機械はいらない.