枚数毎の最大素数大富豪素数を求める

こちらは素数大富豪 Advent Calendar 2016 12日目の記事です。
11日目は鯵坂もっちょさんの「パッと見素数」に気をつけろ！でした。意外と 2 桁でも九九に出てこないと間違えやすいですよね。2 桁の素数は 21 個なので全部覚えるのも 1 つの方法かもしれません。

はじめに

さて、私は以前、tsujimotter 氏の Twitter での発言を見て最大素数大富豪素数を求めてみました。ついでに言うとこの時に初めて素数大富豪を知りまして、いまだに素数大富豪をやったことはありません。

素数大富豪素数の最大値 - Qiita 大元はおそらく 「素数大富豪」に手として出しうる素数を「素数大富豪素数」と名前をつけたとして、...

せっかくゲーム内で出し得る最大の素数を求めたので、今回はもっと少ない枚数でも出せる最大の素数を求めてみようと思いました。タイトルが内容のネタバレですね。先行研究？としてはせきゅーんさんの

1213：素数大富豪における２枚出し最強素数 - インテジャーズ 1213は素数大富豪で２枚出しをする際の最強の素数。...

131311：３枚出し最強素数（素数大富豪） - インテジャーズ 131311131311 は素数大富豪における３枚出し最強素数です。...

と二世さんの

素数大富豪徹底攻略！～ビギナー編～ - にせいの日記 標記の内容について、2月21日(日)の第1回日曜数学会in札幌で...

あたりですかね。あまり先行研究の調査はしてません。どこかで重複してたらごめんなさい。

素数大富豪のルール抜粋

この Advent Calendar をシリーズで読まれている方には必要ないとは思いますが、この記事で解きたい問題の前提条件を明確にするために改めて素数大富豪のルールから一部を抜粋しておきます。

• 使うトランプのデッキは Joker 2 枚を含む全 54 枚
• 10進数の数としてつなげた結果が素数であれば、複数枚同時に出すことができる
• A, J, Q, K はそれぞれ 1, 11, 12, 13 として扱う
• Joker は 0~13 の任意の整数として扱うことができ、2 枚同時に使っても異なる数として扱って構わない
• 大きな数が強い。ただし場に出ているものと同じ数のカードを使って構成する必要がある

求め方

基本的な求め方は最大素数大富豪素数を求めたときと同じように

1. デッキの内 $n$ 枚使えそうなのをピックアップする
2. 選び出した $n$ 枚を並べ替える
3. 素数であるか確認する

という風にしています。($n=1,2,3,\cdots,54$)。ただし、これを素直に行うと計算が終わりそうにないので適当な工夫を入れています。

Joker の設定を 3 つ用意しておく

今回、Joker が "K と Q が 1 枚ずつ"、"両方とも K"、"両方とも Q" という設定にした 3 つのデッキセットを用意しました。というのも、Joker の設定次第ではどう並べても素数にならなかったり、大きな素数がなかったりするからです。それぞれのデッキでの最大素数があればそれを求め、その中で最も大きいものを出力するようにしています。

選び出した n 枚が 3 か 11 の倍数になるか確認する

選びだしたカード次第ではどのように並べても合成数になるものがあります。分かりやすいのは 3 の倍数で、現れる数字の組み合わせが変わらないので 3 で割った余りも変わりません。この場合、並べ替えすらスキップします。
また、それなりに多いカードを使う場合は上の桁のカードを並べ替える必要は殆どありません。逆に言えば並べ替えるカードは下位に来るカード、具体的には 10、J、Q だけになります。その結果 2 桁ずつの入れ替えになっているので、ある並び順で 11 の倍数であればその他の並べ方でも 11 の倍数になることが分かります。($100^ka \bmod 99 = a$ という計算から 99 での余りが変わらない。) ただ、あくまで 2 桁のカードだけを並べ替える場合の工夫なので、A が絡んでくる 51 枚以上では 11 の倍数確認は使えません。

並べ替える順番

最大素数大富豪素数を求めたときと同じ話になりますが、A が絡まない場合は カードを文字列として捉えて「大きい」方から並べ替えると、繋げたときの数が大きい順になります。なので素数になる並び順が見つかれば その後の並べ替えは必要ありません。
一方で A が入ってくると最大素数大富豪素数を求めたときと同じように A, 10, J の組み合わせを全パターン並べ替えることになります。

結果

ということで出来上がったプログラムがこちらで、その実行結果がこちらです。

枚数	最大素数大富豪素数
1	13
2	1213
3	131311
4	13111211
5	1313121311
6	131313131011
7	13131313131113
8	1313131313121013
9	131313131313101011
10	13131313131312121211
11	1313131313131112111111
12	131313131313121211121011
13	13131313131312121110111211
14	1313131313131212101210101111
15	131313131313121212111012101111
16	13131313131312121211121011111011
17	1313131313131212121112101011111011
18	131313131212121212121110101011101111
19	9131313131312121212121111111010101011
20	99131313131212121212111111101010101211
21	999131313131312121212121111101010101111
22	9999131313131212121212111111121010101011
23	99998131313131313121212121110111011101011
24	999988131313131313121212121010111010111111
25	9999888131313131312121212121110101110111011
26	99998888131313131313121212111210101011111011
27	999988887131313131312121212121010111011111011
28	9999888877131313131313121212121110101111101011
29	99998888777131313131313121212121010111011101111
30	999988887777131313131212121212121010101111111011
31	9999888877776131313131312121212121111101011101011
32	99998888777766131313131212121212121110111010111011
33	999988887777666131313131312121212121110101110111011
34	9999888877776666131313131212121212111210101111101011
35	99998888777766665131313131313121212111210101111101011
36	999988887777666655131313131313121212111010111011101211
37	9999888877776666555131313131312121212111211101011101011
38	99998888777766665555131313131313121212111211101011101011
39	999988887777666655554131313131312121212121111101110101011
40	9999888877776666555544131313131313121212111111101210101011
41	99998888777766665555444131313131313121212111211101010111011
42	999988887777666655554444131313131212121212101111101210111011
43	9999888877776666555544443131313131312121212121011101011111011
44	99998888777766665555444433131313131212121212111112101010101111
45	999988887777666655554444333131313131212121212101112111010111011
46	9999888877776666555544443333131313131212121212121010101111111011
47	99998888777766665555444433332131313131313121212121010111110111011
48	999988887777666655554444333322131313131313121212111211101010111011
49	9999888877776666555544443333222131313131312121212121010101110111111
50	99998888777766665555444433332222131313131313121212111112101110101011
51	999988887777666655554444333322221313131313121212121211101110111011011
52	9999888877776666555544443333222213131313131312121212111110111010101111
53	99998888777766665555444433332222131313131313121212121111111011010101111
54	999988887777666655554444333322221313131313121212121211111111101110110101

$n=53$　だと最大素数大富豪素数の

99998888777766665555444433332222131313131313121212121111111011010101111

が出てるのが確認できますね。あと $n\leq20$ では二世さんの記事と同じっぽいです。

おわりに

この問題、あくまで計算問題として求めてはみましたが、そもそもカード枚数として 27 枚以上は相手側が同じ枚数を出せない(正確には27 枚だと相手側は出せるが、その時点で手札が無くなり勝敗がつく)ので「最強」であることに意味がありませんし、54 枚は出す機会すらありませんね。

ではでは Advent Calendar の 13 日目は二世さんの記事になります。2 枚出し最強カードの日付、どんな話が出るのでしょうか。