メルセンヌ素数の系列は計算機による最大素数の発見の歴史でもある。エウクレイデスの時代から素数に上限はないことが知られている。しかし、その時代において分かっている最大の素数というのはある。
その最大の素数は、ほとんどの場合、メルセンヌ素数であったし、これからもそうであり続けるだろう。
というのも、その表記は Mp=2^p−1という、これ以上無いほどのシンプルな表式であり、しかも強力な素数発見アルゴリズムであるリュカ・テストが付随しているからだ。ちなみにpが素数の場合にだけMpは素数になりうる。
GIMPS(Great Internet Mersenne Prime Search)にPCを繋げば、誰でも最大素数発見に参加できる。1996年以後の最大素数の発見はほとんどGIPMSの快挙である。そのメンバーには高校生も含まれる。
PCが20万台以上(最近はどうも減少しているようだ)参加しているその並列処理もリュカ・テストにもとづいているであろう。
*1
Mpが素数となる、そのpの列は2018年1月時点では下記のようなリストになる。
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, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917
さて、これに対応する西暦表示での発見年のシリーズはこうなる。
- 430, -430, -300, -300, 1456, 1588, 1588, 1772, 1883, 1911, 1914, 1876, 1952, 1952, 1952, 1952, 1952, 1957, 1961, 1961, 1963, 1963, 1971, 1978, 1979, 1979, 1982, 1988, 1983, 1985, 1992, 1994, 1996, 1996, 1997, 1998, 1999, 2001, 2003, 2004, 2005, 2005, 2005, 2006, 2008, 2009, 2008, 2013, 2015, 2017
単調増大でないのが玉にキズだが、後から判明したメルセンヌ素数が混じるためだ。
その発見年を横軸にとり、縦軸をメルセンヌ素数Mpの大きさ(対数)にする。
近世に入って桁数が爆発的増大を開始した。もちろん1878年にリュカがその素数判定法を見つけたのは大きい。しかし、20世紀後半がやはり著しい伸びを示す。計算機の参入によるものなのは言うまでもない。
その勢いは1990年台に最大となったように見える。スーパーコンピューターやネットワークによる並列処理の貢献によるものだろう。
だが、2010年代は飽和してきているような気配があるのだ。つまりは、計算テクノロジーも成熟期に入ったことも物語っているのだろう。量子コンピュータの利用など抜本的な革新がなければ、此のままフラットになることは確実だ。
【参考文献】
リュカ・テストについて誰でもわかりやすく説いているのが和田秀夫の本だ。日本(日本語)ではじめての解説だったらしい。
- 作者: 和田秀男
- 出版社/メーカー: 岩波書店
- 発売日: 1981/07/10
- メディア: 単行本
- この商品を含むブログを見る