紀元前300年ごろ、素数が無限に存在することを証明したのは、ギリシャの数学者ユークリッドだったかもしれない。しかし最近になって「これは素数ですか？（Is this prime?）」というコンピューターゲームを考案したのは、英国の数学者であるクリスチャン・ローソン=パーフェクトだ。

5年前に公開されたこのゲームは、2021年7月16日に試行回数300万回を突破した。もっと言えば、掲示板サイトの「ハッカーニュース（Hacker News）」で紹介されたことで試行回数が一気に10万回増え、299万9999回に近づいたのだ。

このゲームでプレイヤーが目指すのは、60秒間でできるだけ多くの数を「素数」と「素数でない数」に仕分けることだ（と、ローソン＝パーフェクトは自身が創設し、編集する数学ブログ「ザ・エイピリオディカル（The Aperiodical）」で説明している）。

素数とは、1とその数自体の2つしか約数をもたない整数のことだ。

「とてもシンプルなのに、腹が立つほど難しいゲームです」と、ニューカッスル大学数学・統計学部のeラーニング部門に所属するローソン＝パーフェクトは言う。空き時間に作ったゲームだが、このゲームは自身の仕事にも役立つことが分かった。ローソン＝パーフェクトはeアセスメント・ソフトウェア（学習評価システム）を作成しているのだ。「私が作っているシステムは、数学の問題をランダムに生成し、生徒から回答を受け取って、自動で正誤判定をし、フィードバックを返すというものです」とローソン＝パーフェクトは言う。「素数を判別するゲームも、一種の評価手段と捉えられるかもしれません」。ローソン＝パーフェクトは、このゲームを遠隔授業に利用している。

ローソン＝パーフェクトがキーボードのショートカットを使えるように手を加えたことで、ゲームはほんの少し簡単になった。マウスを動かす手間を省くために、ｙとｎのキーがスクリーン上のｙｅｓ／ｎｏボタンと連動するようにしたのだ。

実際にやってみよう。

 

 

素数判定のアルゴリズム

素数はコンピューティング（エラー訂正コードや暗号化など）の分野で実用性がある。しかし、素因数分解が難しい（だからこそ、暗号化の分野で価値が高い）一方で、素数の判定は、扱いにくさはあるものの簡単に実行できる。フィールズ賞を受賞したドイツの数学者アレクサンドル・グロタンディークが57を素数だと勘違いしたのは有名な話だ（57は「グロタンディーク素数」と呼ばれている) 。ローソン＝パーフェクトがゲームのデータを分析したところ、さまざまな数にある一定の「グロタンディーク性」が見られることが判明した。最もよく素数に間違われていた数は51で、以下57、87、91、119、133と続く。ローソン＝パーフェクトの宿敵だ（彼はまた、便利な素数判定サービスも考案している）。

ある数が素数かどうか判定する方法として最もシンプルなのは「試し割り法」、つまり、その数を平方根までのすべての数で割っていく方法だ（平方根より大きい2つの数の積は、判定対象の数よりも大きくなる）。

しかし、この素朴なやり方はあまり効率がいいとはいえず、何世紀ものあいだに編み出されてきた他の手法にしても、非効率なことに変わりはなかった。ドイツの数学者カール・フリードリッヒ・ガウスが1801年に述べたとおり、素数の判定には「どんなに疲れ知らずの計算機械でも耐え切れないほどの労力が要る」のだ。

ローソン＝パーフェクトがこのゲームを開発するのに使ったアルゴリズムは、「ミラー－ラビン素数判定法」と呼ばれるものだ（ミラー－ラビン素数判定法は、効率面で優れているものの、厳密ではない17世紀の手法「フェルマーの小定理」に基づいている）。ミラー－ラビン素数判定法は、驚くほどうまく機能した。ローソン＝パーフェクトが知る限り、それは「ほとんど魔法のよう」であり。「どんな仕組みで動いているのかよくは分かりませんが、時間をかけてもっと詳しく調べてみれば理解できるはずです」と言う。

この判定法にはランダム性が利用されているため、得られる結果は確率的なものだ。つまり、誤った判定結果が出る場合もある。ダートマス大学の数学者で書籍「素数全書―計算からのアプローチ（原題はPrime Numbers: A Computational Perspective）」の共著者のカール・ポメランス教授は「インポスター、つまり、素数を装った合成数を素数と判定してしまう可能性があるのです」と語る。しかし、アルゴリズムの巧妙なチェック機構をすり抜けて誤判定が出る可能性は1兆分の1程度であり、ミラー－ラビン素数判定法は「極めて信頼性が高い」と言う。

しかし、巧妙な素数判定アルゴリズムとしては、ミラー－レビン判定法は「氷山の一角」だとポメランス教授は述べている。その顕著な例が、19年前、インド工科大学カンプール校の3人のコンピューター科学者、マニンドラ・アグラワル、ニラジュ・カヤル、ナイティン・サクセナが発表した、（やはりフェルマーの小定理を基にした）AKS素数判定法だ。これによって、ある数が素数であることを、ランダム化を用いず、（少なくとも理論的には）驚異的な速さで明確に証明する方法がついにもたらされた。しかし、理論上の速さが実際のスピードと一致するとは限らず、AKS判定法は実用的には役に立たない。

非公式の世界記録

だが、実用性が常に重要となるわけではない。ローソン＝パーフェクトのもとには時折、ゲームでハイスコアを出したことを共有したいという熱心な人たちからメールが届く。最近はあるプレイヤーが60秒間で60回の仕分け記録を出したが、最高記録はどうやら127回のようだ。（ローソン＝パーフェクトはハイスコアのトラッキングをしていない。コンピューターを使った不正行為でデータの中に突出して高いスコアが生じることから、不正プレイヤーがいると分かっているからだ）。

127点というスコアを出したのは、ラヴィ・フェルナンドというカリフォルニア大学バークレー校数学研究科の大学院生で、2020年7月にプレイ結果を投稿した。このスコアはフェルナンドの自己ベストで、彼自身はこれを「非公式世界記録」だと考えている。

2020年夏以降、フェルナンドはデフォルト設定ではこのゲームをあまりプレイしていないが、より大きな数字を表示したり、制限時間を長くしたりできるカスタマイズ設定では、5分の制限時間で240点を獲得した。「出てくる数の範囲が4桁代の後半まで広がるので、かなりの部分を推測しなければなりませんでした。私は3000代前半くらいまでの素数しか覚えていないんです」とフェルナンドは言う。「それでも十分やり過ぎという人もいるでしょうけどね」。

フェルナンドは代数幾何学を研究しているが、素数もある程度関わっている。しかしフェルナンドは「研究はどちらかというと、ゲームをやり始めたきっかけよりもゲームをやめたきっかけの方に関係しています」と言う（彼は2014年に博士課程を開始した）。さらにフェルナンドは、127という記録を更新するのは非常に難しいと考えている。127が素数であることから、「素数の最高記録でやめておくのがちょうどいい気がします」とフェルナンドは言う。

• 48
• 5

人気の記事ランキング

1. This US startup makes a crucial chip material and is taking on a Japanese giant 知られざる半導体材料の巨人 「味の素」の牙城を狙う 米スタートアップの勝算
2. Why it’s so hard for China’s chip industry to become self-sufficient 中国テック事情：チップ国産化推進で、打倒「味の素」の動き
3. Researchers taught robots to run. Now they’re teaching them to walk 走るから歩くへ、強化学習AIで地道に進化する人型ロボット
4. How thermal batteries are heating up energy storage レンガにエネルギーを蓄える「熱電池」に熱視線が注がれる理由