「賞金を素数にしてみました!」にみる、俺たちエンジニアが素数に惹かれる理由

2013年12月18日に、株式会社リクルートホールディングスと米Indeed社が開催した「Recruit Programming Contest」をご存じでしょうか?

このコンテストでは、競技開始と同時にいくつかの「難問」が提示され、それを限られた時間でどれだけクリアできるかを競うものでした。この様子はギズモードでも取りあげられており、多くの参加者が超難問に取り組んでいました。

このコンテスト、出題された問題の難しさもさることながら、一番目を引いたのは実は「賞金」。1位になると頂上決戦として、アメリカに渡り有名大学とのコンテストに出場できたり、Indeed社エンジニアとの交流会に参加できたりととてもうれしい内容でしたが、その賞金は見ての通り、ちょっとおかしいことになってます。

賞金 : 下記の通り
1位: ¥299,993
2位: ¥199,999
3位: ¥149,993
4位: ¥99,991
5位: ¥79,999
6位: ¥59,999
7位: ¥39,989
8位: ¥29,989
9位: ¥19,997
10位: ¥9,973

この金額にピクっときたら、あなたは間違いなくエンジニアでしょう。そう、これ「素数」なんですよ! 素数と言えば数学界の神秘。素数と言えば心躍る。ああ、素数、愛してるよ素数……申し訳ありません。取り乱しました。

■そもそも「素数」ってなんだ?!

そもそも素数の定義とは、皆さんもご存じのように「1と自分自身以外に、正の約数を持たない」という特殊な数字。たとえば「3」は、1と3以外に割り切れる数字がありませんから素数です。2,3,5,7,11,13,19……と、バラバラな間隔で素数は登場します。このあたりは、子供のころに習った内容ですね。

素数の特徴は、「素因数分解が難しい」こと。例えば「736163」をぱっと素因数分解できますでしょうか(正解は857と859)。でも、857と859を掛け合わせるのは一瞬です。この仕組みをうまく使っているのが「暗号化」。RSA暗号はけた数が大きい素数の素因数分解が難しいことを利用しています。私たちが普段使っているSSL通信なんかも、素数をうまく使った例なのです。

ところで、素数は計算で見つけることは可能なのでしょうか。これは大議論をうむ命題として、数学界にいまだ残る「難問」となっています。一見無秩序に表れる素数に、なんらかの規則性があるのではないかと数学者は考えています。素数の規則性につながるとされているのが、数学界にいまだ横たわる難問「リーマン予想」……。数学は美しい、という大前提のもと、数学が哲学に変わるかのような存在、それが素数なのです。

では、素数に関係したいくつかの知識を。

■素数には規則性があるかも?「ウラムの螺旋」

「素数に規則性なんてないんじゃないの?」と思う方も多いでしょう。では、こちらをご覧下さい。

ulam1

この図は、1から50までの数字をぐるぐるとらせん状に配置したもの。これを素数だけ取り出すと……。

ulam2

なんと、なぜか素数は対角線に沿って配置されているものが多いではありませんか。さらにこれを200×200まで拡張して配置すると、こんなふしぎな図が書けます。

ulam3
wikipediaから引用)

あれ、なぜか直線が見え隠れしますね。もしかしたら規則性があるのかも……と思える図。これは発見者の名前を取り「ウラムの螺旋」と呼ばれる図で、素数の神秘が一目で分かる図になっています。

■なんとなく神秘性がある?「メルセンヌ素数」

数学界にはメルセンヌ数というものがあります。これは「(2のn乗)-1」で表現できる数字のこと。なにがなにやら? と思うかもしれませんが、これは実は2進数で考えると、「1がズラリと並ぶ」数字にほかなりません。要するに「127」(n=7)や「255」(n=8)や「65535」(n=9)のこと。ほら、身近に感じてきたでしょ?

で、このメルセンヌ数のうち、素数であるものを集めたのが、「メルセンヌ素数」。いまのところ、48個まで知られています。その48個とは……。

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951

2の2乗-1は3だから、2はメルセンヌ素数、2の3乗-1は7だから、3もメルセンヌ素数……。さて問題、いまのところは48個ですが、これ以上のメルセンヌ素数は存在するのでしょうか? そしてその数は有限なのか、はたまた無限なのか……。これは、今も数学界の未解決問題として残っています。ロマン!

■2つしか離れてない「双子素数」

素数にはまだまだ特別な名前が付いたものが多くあります。その一つが「双子素数」。これは素数同士が2しか離れていないもの。3と5、5と7、11と13……などが存在します。先ほど例にだした、857と859も双子素数ですね。

2しか離れていないなら、そんなに大きな数はないのかな、と思いますよね。実はいまのところ発見されている最大の双子素数は、なんと20万700桁もあります。この双子素数は無限に存在するのか?という問題も、現時点では未解決。

さて、皆さんも素数の魅力に気が付きましたでしょうか? さらに素数を知りたい,という方は、2009年に放送されたNHKスペシャル「魔性の難問 リーマン予想・天才たちの闘い」をお勧めします。オンデマンドで見られますのでぜひ。これからのエンジニアはガンダムやエヴァだけでなく、素数の知識でも会話が弾むべき! きっと、Recruit Programming Contestの賞金もそのような意図があったのでしょう。あったはずです!(断言)