レーマーふるい

レーマーふるいは、数論におけるふるいを実装する機械装置です。レーマーふるいは、デリック・ノーマン・レーマーとその息子デリック・ヘンリー・レーマーにちなんで名付けられました。父親は当時、 カリフォルニア大学バークレー校の数学教授であり、息子は父親の跡を継ぎ、数論学者およびバークレー校の教授になりました。

ふるいは一般的に、一組の数を別の組の数で割ったときに余りとなる数を見つけることを目的としています。一般的に、ふるいはディオファントス方程式の解を求めるときや数を因数分解するときに使用されます。レーマーふるいは、特定の構成に応じてさまざまな方法でそのような解が見つかることを示します。

1926年に初めて作られたレーマーふるいは、長さの異なる自転車のチェーンと、チェーンの適切な位置にロッドを使用して作られました。チェーンが回転すると、ロッドが電気スイッチを閉じ、すべてのスイッチが同時に閉じて完全な電気回路を作成すると、解決策が見つかりました。レーマーふるいは非常に高速で、ある特定のケースでは因数分解が行われました。

${\displaystyle 2^{93}+1=3\times 3\times 529510939\times 715827883\times 2903110321}$

3秒で。^[1]

1932 年に作られた歯車を使った装置が、シカゴで開催された世紀の進歩博覧会で展示されました。この装置には、以前のチェーンと同じように、穴の開いた数字を表す歯車がありました。空いた穴は、求める剰余です。穴が一列に並ぶと、装置の片端の光がもう一方の光電セルに当たり、機械を停止して解を観察することができます。この装置では、1 秒間に 5,000 通りの組み合わせをチェックできました。

1936 年には、チェーンの代わりに16 mm フィルムを使用し、ロッドの代わりにフィルムに穴をあけたバージョンが作られました。穴が上に達すると、ローラーに当たるブラシが電気的に接触します。この場合も、穴が完全に連続すると完全な回路が形成され、解決策が示されました。

コンピュータ歴史博物館には、レーマーのふるいがいくつか展示されています。それ以来、同じ基本的な考え方が集積回路やソフトウェアのふるいの設計に使用されてきました。^[要出典]

• エラトステネスの篩

• Lehmer, DN (1932)、「数論における大物狩り」、Scripta Mathematica、1 : 229–235。
• Lehmer, DH (1928)、「線形形式の機械的結合」、アメリカ数学月刊誌、35 (3)、アメリカ数学協会: 114–121、doi :10.2307/2299504、JSTOR  2299504アンティークコンピュータのホームページでもオンラインでご覧いただけます。
• ベイラー、アルバート H. (1964)、数論におけるレクリエーション、ドーバー、第XX章、XXI章。
• ウィリアムズ、マイケル R. (2002)、レーマーふるい。

• コンピュータ歴史博物館主任学芸員マイケル・R・ウィリアムズ博士によるレーマーふるい
• コンピュータ歴史博物館のレーマーふるい（ページ下部）