問題定義
大元はおそらく
「素数大富豪」に手として出しうる素数を「素数大富豪素数」と名前をつけたとして、その素数大富豪素数は果たしてどの程度存在するだろうか。
— tsujimotter (@tsujimotter) 2014, 12月 22
これを「素数大富豪素数問題」という（いわない）
— tsujimotter (@tsujimotter) 2014, 12月 22
という @tsujimotter 氏の発言で、（素数大富豪のゲームルールではなく）問題の要点を整理すると
- トランプの52枚＋ジョーカー2枚の合計54枚からいくつか取り出す。ただし54枚全て取り出すことはできない。
- そのカードを並べ、10進数の数(ただしJ=11,Q=12,K=13,A=1とし、Jokerは0以上13以下の任意の整数を取れる）としてつなげ、1つの数として見る。 （例："3" "J" "A" → 3111、"7" "Joker" → 75、"7" "Joker" → 711)
- 出来上がった数が素数となる
という条件の元で、最大の数はなにか？ ということになる。この問題をコンピュータプログラムで解く前提で考えたい。
ちなみに素数大富豪のルールについては せきゅーん氏(@integers_blog)のブログ記事が詳しい。
解答方針
正解の候補を見つける
そもそも、素数大富豪で出せそうなパターンは…具体的な数はともかくとして、とにかく多そうである。それらを全て挙げていってもこの問題の助けにはならない。なのでまずは正解の存在する範囲を絞りたい。
そこで今回の問題で「条件を満たす最大値」を求めたいので、「条件を満たすかどうか分からない、大きそうな候補」を調べることで正解の候補を絞ることにした。具体的には
- 素数という制限を無視する(ただし 3 の倍数に関する条件だけ確認)
- 使うカードは A 1 枚を除いた 53 枚 (A)
- Joker は 2 枚とも 13 ということにする (B)
- 大きそうな数から順に素数判定にかける
ということになる。素数と判定される数が出たら正解候補が出たということでこの段階は終了となる。ちなみに最後まで素数判定が出なかったら (A) や (B) の条件を変更して行くことになるが、そもそも上記の設定でも全部列挙するのは現実的な時間で終わらないだろう。
具体的な正解を探る
次に具体的な正解の数を求めることになる。
上記の方法で 1 つ具体的な候補が挙げられたので、それを元に正解(と正解候補)を含む範囲を絞り、全て確認するということになる。方法自体が出てきた候補に強く依存するので詳細については下記をご覧頂きたい。
候補探索
前提
そもそも、2つの正整数を比較した時、どのように大小を比較できるかというと
- 桁数が違ければ、桁数が多いほうが大きい
- 桁数が同じならば、上の桁から比較していき、最初に異なる桁において大きな数字を持つほうが大きい
という風になる。 なので、
- 使う枚数はできるだけ多い方が良い。
- Joker は 13 に設定する方が良い。（2桁にすることで桁数が伸びる＆13がその条件下で最も大きい）
ということを利用する。<追記>実際に実験するときには配慮しそびれていたのだが、このとき使うカードはA(=1)が3枚、K(=13)がJokerを含んで6枚、他は4枚ずつとなるので、このカードセットは3の倍数にならないことが保証されている。</追記>
実験
この設定に基づいて検証したプログラムが
https://gist.github.com/peria/00e294247aa4226a82f2#file-largest_dpn_71dig-cc
である。 12-18 行目で使うカードを設定し、19行目以降で探索を行っている。アルゴリズムとしては
- カードの数字を文字列として見て辞書順に降順に並べる
- カードををつなげて数を作る
- できた数が素数かどうか判定する
- カードの並びを辞書順での次の並び方に変えて 2. に戻る
というだけである。概要部分にも書いたとおり、そもそも目的としている素数が71桁ではなかったり、辞書順で見て序盤に無かったりすると死ぬ方法であるが、実際には 1 つの数がすぐに出てくる。
99998888777766665555444433332222131313131313121212121111111011010101111
確定事項
この数が出力されたことにより、求めたい数について以下のことが判明した。
- 求める素数は 71 桁である
- 上記の数以上の数である
後者に関してはカードの辞書順と、つなげてできる数との大小関係が異なるパターンがあることに起因する。具体的には A と 10 を並べる時、カードを辞書順で比較する方法とつなげた数で比較する方法とで順序が入れ替わることに原因がある。
例えば [A, 10] と [10, A] を比較すると、カードの並びで見る場合、先に "1" < "10" が比較されるため前者は後者より小さい。一方、つなげた数で見た場合 $110>101$ となるため前者は後者より大きいと判断される。
つまり、先ほど候補に挙げられた 71 桁の数はカードの辞書順で言えば最大であったのだが、つなげた数としての最大性は保証されていない。ただ幸いなことに、この順序関係が入れ替わりうる部分は末尾数桁（A,10,11の並び方が変わる部分）に絞られるので、その部分だけ全探索することで確認することが可能である。
そのコードがこちら。
https://gist.github.com/peria/00e294247aa4226a82f2#file-largest_dpn-cc
カード順序で見ても数の順序で見ても変わらない、かつ最大となっている $999\cdots1212$ の部分を固定し、順序が変化し得る残りの部分を全パターン組み合わせて確認している。
実際には先ほど得ていた候補を元に、それ以上の素数があれば出力するようにしている。が、動きとしては他の数が出てこないので、やはり先程得た
99998888777766665555444433332222131313131313121212121111111011010101111
が最大の素数大富豪素数ということになる。
<追記>重箱の隅をつつくと、このプログラムの中では Miller-Rabin の確率的素数判定法を使っているため $4^{-100}$ 程度の確率で合成数かもしれない。が、そのような数は確定的素数判定をしてくれるサービスに投入すれば素数であることを教えてくれるので適宜探ってご利用いただきたい。</追記>
類題
類題に 素数大富豪素数ではない最小の素数問題 ってのもありますが、ちょっと大変そうな類題は "素数大富豪で出せる最大の合成数を求めよ" だと思います。冒頭で挙げたルールでは何も書いてないですが、合成数を出す場合には素因数分解をする必要があり、かつその素因数も全て同時にカードで作らなきゃならないので、上界の35桁を構成できるのか気になります。
考察
その1
素数定理からすると、テキトーに与えられた数 $x$ が素数である確率は $1/\ln x$ であり、
\ln (9.999 \times 10^{70}) \simeq 163.483441598
ということを考えると、最初から順序関係が怪しい A, 10, J の箇所だけ並び替える作戦でも良かったんじゃないかなとふと思った。ちなみに A, 10, J の並べ替えパターン数は(高校数学)
{}_{11}C_3\cdot{}_8C_4\cdot{}_4C_4 = 11550
なので確率的には 70 個くらい、もっと言えば 10 が末尾に来る確率が 1/2 じゃない、そもそも 3 の倍数でないことが保証されているなど補正がかかるのでそれ以上みつかってもおかしくないなぁ…と思って実験してみたところ、該当パターン内で素数になる並べ方が 94 種類発見されました。（ただし [J, A] と [A, J] の並びを区別してカウントしているので、出てくる数自体はもっと少ない。）