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

こちらは[素数大富豪 Advent Calendar 2016](http://www.adventar.org/calendars/1663) 12日目の記事です。
11日目は[鯵坂もっちょ](https://twitter.com/motcho_tw)さんの[「パッと見素数」に気をつけろ！](http://motcho.hateblo.jp/entry/2016/12/11/190626)でした。意外と 2 桁でも九九に出てこないと間違えやすいですよね。2 桁の素数は 21 個なので全部覚えるのも 1 つの方法かもしれません。

## はじめに
さて、私は以前、[tsujimotter 氏](https://twitter.com/tsujimotter)の Twitter での発言を見て最大素数大富豪素数を求めてみました。ついでに言うとこの時に初めて素数大富豪を知りまして、いまだに素数大富豪をやったことはありません。

<TABLE ALIGN=CENTER><TR><TD WIDTH=400px>
 <A HREF="http://qiita.com/peria/items/595783484aad2698ad67" TARGET="_blank"><STRONG>素数大富豪素数の最大値 - Qiita</STRONG></A>
 <A HREF="http://b.hatena.ne.jp/entry/http://qiita.com/peria/items/595783484aad2698ad67" TARGET="_blank">
 <IMG BORDER="0" SRC="http://b.hatena.ne.jp/entry/image/http://qiita.com/peria/items/595783484aad2698ad67" BORDER="0" ALT="" /></a>
 <BR>
 大元はおそらく<br>
「素数大富豪」に手として出しうる素数を「素数大富豪素数」と名前をつけたとして、...
 </TD>
 <TD WIDTH=150px>
 <IMG STYLE="float:left;margin-right:.5em;" SRC="http://capture.heartrails.com/120x120/cool?http://qiita.com/peria/items/595783484aad2698ad67" ALT="" WIDTH="120" HEIGHT="120" />
 </TD></TR>
</TABLE>

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

<TABLE ALIGN=CENTER><TR><TD WIDTH=400px>
 <A HREF="http://integers.hatenablog.com/entry/2015/12/13/032031" TARGET="_blank"><STRONG>1213：素数大富豪における２枚出し最強素数 - インテジャーズ</STRONG></A>
 <A HREF="http://b.hatena.ne.jp/entry/http://integers.hatenablog.com/entry/2015/12/13/032031" TARGET="_blank">
 <IMG BORDER="0" SRC="http://b.hatena.ne.jp/entry/image/http://integers.hatenablog.com/entry/2015/12/13/032031" BORDER="0" ALT="" /></a>
 <BR>
 1213は素数大富豪で２枚出しをする際の最強の素数。... 
 </TD>
 <TD WIDTH=150px>
 <IMG STYLE="float:left;margin-right:.5em;" SRC="http://capture.heartrails.com/120x120/cool?http://integers.hatenablog.com/entry/2015/12/13/032031" ALT="" WIDTH="120" HEIGHT="120" />
 </TD></TR>
</TABLE>
<TABLE ALIGN=CENTER><TR><TD WIDTH=400px>
 <A HREF="http://integers.hatenablog.com/entry/2016/01/31/000000" TARGET="_blank"><STRONG>131311：３枚出し最強素数（素数大富豪） - インテジャーズ</STRONG></A>
 <A HREF="http://b.hatena.ne.jp/entry/http://integers.hatenablog.com/entry/2016/01/31/000000" TARGET="_blank">
 <IMG BORDER="0" SRC="http://b.hatena.ne.jp/entry/image/http://integers.hatenablog.com/entry/2016/01/31/000000" BORDER="0" ALT="" /></a>
 <BR>
 131311131311 は素数大富豪における３枚出し最強素数です。... 
 </TD>
 <TD WIDTH=150px>
 <IMG STYLE="float:left;margin-right:.5em;" SRC="http://capture.heartrails.com/120x120/cool?http://integers.hatenablog.com/entry/2016/01/31/000000" ALT="" WIDTH="120" HEIGHT="120" />
 </TD></TR>
</TABLE>

と[二世](https://twitter.com/m_2sei)さんの

<TABLE ALIGN=CENTER><TR><TD WIDTH=400px>
 <A HREF="http://nisei.hatenablog.com/entry/sun_math_1" TARGET="_blank"><STRONG>素数大富豪徹底攻略！～ビギナー編～ - にせいの日記</STRONG></A>
 <A HREF="http://b.hatena.ne.jp/entry/http://nisei.hatenablog.com/entry/sun_math_1" TARGET="_blank">
 <IMG BORDER="0" SRC="http://b.hatena.ne.jp/entry/image/http://nisei.hatenablog.com/entry/sun_math_1" BORDER="0" ALT="" /></a>
 <BR>
 標記の内容について、2月21日(日)の第1回日曜数学会in札幌で... 
 </TD>
 <TD WIDTH=150px>
 <IMG STYLE="float:left;margin-right:.5em;" SRC="http://capture.heartrails.com/120x120/cool?http://nisei.hatenablog.com/entry/sun_math_1" ALT="" WIDTH="120" HEIGHT="120" />
 </TD></TR>
</TABLE>

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

## 素数大富豪のルール抜粋
この Advent Calendar をシリーズで読まれている方には必要ないとは思いますが、この記事で解きたい問題の前提条件を明確にするために改めて[素数大富豪のルール](http://integers.hatenablog.com/entry/2016/10/10/193619)から一部を抜粋しておきます。

- 使うトランプのデッキは 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 の組み合わせを全パターン並べ替えることになります。

### 結果

ということで出来上がったプログラムが[こちら](https://gist.github.com/peria/a74a0c809b5a4231abc3f4a94f07131a)で、その実行結果がこちらです。

|枚数|最大素数大富豪素数|
|---:|----------------:|
| 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$ では[二世さんの記事](http://b.hatena.ne.jp/entry/http://nisei.hatenablog.com/entry/sun_math_1)と同じっぽいです。

## おわりに

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

ではでは Advent Calendar の 13 日目は[二世](https://twitter.com/m_2sei)さんの記事になります。2 枚出し最強カードの日付、どんな話が出るのでしょうか。