ラマヌジャン革命について/素数大富豪日記11月編

素数大富豪 Advent Calendar 2016十四日目です。昨日はにせいさんの「12月13日は素数大富豪の日」です↓ http://nisei.hatenablog.com/entry/2016/12/13/204650 今日はラマヌジャン革命に秘められた数学的な美しさについて、素数大富豪日記11月編を兼ねてまとめて書くことにします。
2
みうら @miura_prime

#素数大富豪 Advent Calendar 2016 12月14日【ラマヌジャン革命について/素数大富豪日記11月編】

2016-12-14 00:26:55
みうら @miura_prime

11月6日。僕はサイエンスアゴラの日曜数学会のブースに行き、もっちょさんの数式お絵かきの話を聞いていました。ブースをはみ出るほどたくさんの人が詰めかけていた発表が終わり、その後僕はもっちょさんとのMATH POWER以来の対談を楽しんでいたのですが……

2016-12-14 00:28:40
みうら @miura_prime

どうしたことでしょう。再びお客さんがブースからはみ出しています。その視線の先には「素数大富豪で遊ぼう」というスライド。そう、狐さんによる素数大富豪の紹介です!

2016-12-14 00:29:17
みうら @miura_prime

素数大富豪がこれから間違いなくメジャーな遊びに発展していくことを確信させてくれるような光景に感動しながら、僕はtsujimotterさんたちと素数大富豪を楽しみました。ラマヌジャン革命が話題になったのは、そのときです。

2016-12-14 00:30:16
みうら @miura_prime

実は僕はtsujimotterさんとの2人対戦では負けてしまったのですが、その後ある中学生を交えて3人対戦をすることになります。その人物こそラマヌジャン革命を考案したスーパー中学生。素数や1729についての魅力を語り合えてとても楽しかったです。

2016-12-14 00:30:55
みうら @miura_prime

さて、そのラマヌジャン革命ですが、革命が起こると小さな素数が重宝され、さらにはジョーカーを0として用いる必要が出てくるなどゲームとしての幅が大きく広がります。しかも1729という4枚出しはそう頻繁には出ないので、ゲームバランス的にも革命が起こる頻度はちょうどいい。

2016-12-14 00:32:12
みうら @miura_prime

僕はサイエンスアゴラで初めてこのルールを聞いたとき、素直に面白いと思いました。しかしそれと同時に、頭にちょっと引っかかるものがあったのも事実です。それは、 1729って「素数っぽい」か? という疑問です。

2016-12-14 00:32:41
みうら @miura_prime

素数大富豪では、合成数は素因数がなければ出せません。唯一の例外はグロタンカットの57で、そのエピソードからもわかるように57は"素数っぽい"数です。 この例外に今、1729という合成数が加わろうとしている。できれば1729も"素数っぽい"数であってほしい。僕はそう思いました。

2016-12-14 00:33:38
みうら @miura_prime

でも、ラマヌジャンのタクシー数1729(=7*13*19)は、素数でないどころか3つの異なる素因数を持ちます。素数との関連というと、せいぜい17と29が両方素数であることくらい(だから何だ)。

2016-12-14 00:34:22
みうら @miura_prime

確かに1729は特別な数ですが、この合成数が素数大富豪において「革命」という役割を担ってしまっていいのだろうか?そう思わずにはいられませんでした。

2016-12-14 00:35:23

サイエンスアゴラでの素数大富豪の話は九日目の狐さんの記事が詳しいですね。
http://wreck1214.hatenablog.com/entry/2016/12/09/063000

みうら @miura_prime

それからおよそ一週間。僕が1729という数を再び耳にしたのは、大学の研究室でした。その日話題になっていたのは「カーマイケル数」という、素数判定アルゴリズムに関係の深い数。フェルマーテストと呼ばれる素数判定を合成数のくせに必ずパスしてしまう"素数っぽい"数です。

2016-12-14 00:37:14
みうら @miura_prime

少し詳しく言いますと、フェルマーテストとは(2以上の)自然数nに対してnと互いに素な自然数aを用意して a^(n-1)≡1 (mod n) が成り立つかを調べるテストです。

2016-12-14 00:42:55
みうら @miura_prime

もしnが素数なら、 nと互いに素な任意の自然数aに対してa^(n-1)≡1 (mod n) (☆) が成り立ちます(フェルマーの小定理)。しかし、合成数のくせに条件(☆)を満たしてしまう数もある。それがカーマイケル数です。

2016-12-14 00:43:28

カーマイケル数についてはtsujimotterさんのブログに詳しく書かれています。
http://tsujimotter.hatenablog.com/entry/carmichael-number

みうら @miura_prime

…やや前置きが長くなりましたので、もうお気づきの方も多いでしょう。ラマヌジャン革命の話なのにカーマイケル数が出てきた理由。それはズバリ、 1729はカーマイケル数 だからです!

2016-12-14 00:48:41
みうら @miura_prime

ゼミで先生がカーマイケル数の例として1729を出したとき僕は正直信じられませんでしたが、調べてみるとカーマイケル数は小さい順に 561,1105,1729,2465,… となっていて、確かに1729が出てきました。さらにカーマイケル数に「絶対擬素数」という別名があることも判明。

2016-12-14 00:49:16
みうら @miura_prime

これはすごい事実です。タクシー数1729は、絶対擬素数というこれ以上ない特徴を持った"素数っぽい"数だったのです!

2016-12-14 00:51:14
みうら @miura_prime

しかし僕が衝撃を受けたのはそこだけではありません。すごいのは、 561,1105,1729,2465,… という数の並びです。素数大富豪において561は(もちろん合成数ですが)3枚で作る数字で、さらに1105も、1,10,5という3枚で作れる数字です。

2016-12-14 00:51:40
みうら @miura_prime

もちろん1105はジョーカーを使えば4枚出しにもできますが、それに対して1729は4枚でしか出せない数。つまりラマヌジャンの1729には、 素数大富豪において4枚を必要とする最小の絶対擬素数 という驚くべき性質があるのです!

2016-12-14 00:52:53
みうら @miura_prime

なお、「絶対擬素数」という呼び方には先ほどの条件(☆)の"互いに素な任意の自然数a"という部分が関係しています。個別の自然数、特にa=2としたときの 2^(n-1)≡1 (mod n) を満たす合成数nを単に「擬素数」と呼ぶことが多く、これは絶対擬素数より弱い条件です。

2016-12-14 00:53:29
みうら @miura_prime

ここでも 2^(n-1)≡1 (mod n) を満たす合成数nのことを擬素数と呼ぶことにすると、擬素数は小さい方から341,561,645,1105,1387,1729,1905,2047,… となります。実は1729のすごさはここにもあります。

2016-12-14 00:55:06
みうら @miura_prime

条件が弱まったことで、1729未満で 341,645,1387 という3つの数が新しく加わりました。しかしこれらも3枚で作れる数です(1387はK87)。すなわち、"絶対"という言葉をつけずに、 1729は素数大富豪において4枚を必要とする最小の擬素数 と言ってもよいのです!

2016-12-14 00:55:36
みうら @miura_prime

1729にはれっきとした"素数っぽい"性質がありました。ラマヌジャンのタクシー数という歴史的事実に加えてこのような数学的特徴を持っている1729は、間違いなく素数大富豪において革命という役割を担うにふさわしいですね。素数大富豪のゲームとしての美しさが感じられます。

2016-12-14 00:57:16
みうら @miura_prime

ラマヌジャン革命がルールに加わることで、素数大富豪で特別な意味を持つ合成数は57と1729の2つになります。そしてこれらがそれぞれ別の意味で"素数っぽい"ことがわかりました。57は「パッと見素数」、1729は「絶対擬素数」ですね。

2016-12-14 00:57:48