「パッと見素数」に気をつけろ！

f:id:motcho:20161211183939p:plain

91は素数でしょうか？

91は素数
— 91は素数 (@91__prime) 2016年8月13日

91は素数ではありません。

素数大富豪

この記事は、素数大富豪Advent calender11日目の記事です。

「素数大富豪」というトランプゲームがあります。通常の大富豪は場に出ているカードより大きいカードをどんどん出していくというものですが、素数大富豪においてはカードを組み合わせて素数を作り（「4」と「1」で「41」みたいな）、場に出ている素数より大きい素数を出していって、先に手札をなくしたほうが勝ち、というルールになってます。詳しいルールはこちらです。

www.ajimatics.com

素数でない数、すなわち合成数を出してしまうとペナルティとして山札からカードを引かなければなりません。

そんなわけなので、素数大富豪において「一見素数に見えてその実、素数でない」91は鬼門なのです。私自身、大事なところで91を出して散ってゆく兵どもを何度もこの目で見てきました。痛ましいことです。なぜそんなに91は素数っぽいのでしょうか？

パッと見素数

素数大富豪初心者がまず覚えるべきなのは100以下の素数です。そこで、100以下の自然数に対して定義される「パッと見素数（glance prime）」という概念を考えました。

91のような「パッと見で素数に見えちゃう数」は以下の五つの条件をみたすはずです。

①下一桁が偶数でない（奇数）

なにはなくともこれです。すなわちその数自体が偶数でないということです。

②下一桁が５でない

その数の下一桁が偶数でなくても、下一桁が５ならばその数は５の倍数であるとすぐにわかるので除くことができます。

③九九に出てこない

その数の下一桁が偶数でも５でもなくても、九九の中に出てくるものであればすぐに合成数だとわかるので除けます（例：27、49、81など）。

④「各桁が両方とも３の倍数」でない

その数の下一桁が偶数でも５でもなくて九九に出てこなくても、二つの桁が両方とも３の倍数なら、その数はすぐに３の倍数であるとわかるので除けます（例：39、69、93など）。

⑤各桁が同じでない

その数の下一桁が偶数でも５でもなくて九九に出てこなくて各桁が両方とも３の倍数でなくても、二つの桁が同じならばその数はすぐに11の倍数であるとわかります（例：77など、ただし11自身は除く）。

以上五つです。この条件は「合成数かどうかがすぐに判断できる要素」と言い換えてもよいでしょう。100以下の自然数において、この五つのふるいをすり抜ける数はなんと四つしかないのです。パッと見素数テストに合格した屈強な合成数の方々がこちら。

51　57　87　91

たしかに91が入ってますね！　「グロタンディーク素数」57も入ってます。

グロタンディーク素数

素数大富豪プレイヤーにはおなじみですが、57に関してはこんなエピソードがあります。

20世紀を代表する数学者であるアレクサンドル・グロタンディーク（Alexander Grothendieck, 1928 - 2014）が、素数に関する講演をしていたとき、聴衆の一人から「抽象的すぎてわかりにくいので、具体的な素数で話してほしい」という意見が出ました。そこでグロタンディークは「そうだな、じゃ57で。」と言ったとか言わないとか言われています。そのため今日では57には「グロタンディーク素数」という称号が与えられています。あれだけの高名な数学者が素数と言ったんだから素数と認めてしまってもいいじゃないか、という一種のジョークですね。

まあぶっちゃけこの話のソースははっきりしないのですが、個々の具体的な事例よりも一般的な理論を愛する数学者の姿勢を表すエピソードとして語られることがあります。このエピソードに敬意を表して、素数大富豪では57に対して特別な役割を与えています（ルール参照）。

グロタンディークほどの天才でも「パッと見素数」に惑わされることがあるということです。前述の「パッと見素数のふるい」の正当性にも箔が付いたというものでしょう。