素数
素数大富豪

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

More than 1 year has passed since last update.

こちらは素数大富豪 Advent Calendar 2016 12日目の記事です。

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


はじめに

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

素数大富豪素数の最大値 - Qiita




大元はおそらく

「素数大富豪」に手として出しうる素数を「素数大富豪素数」と名前をつけたとして、...



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

1213:素数大富豪における2枚出し最強素数 - インテジャーズ




1213は素数大富豪で2枚出しをする際の最強の素数。...



131311:3枚出し最強素数(素数大富豪) - インテジャーズ




131311131311 は素数大富豪における3枚出し最強素数です。...



二世さんの

素数大富豪徹底攻略!~ビギナー編~ - にせいの日記




標記の内容について、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 枚出し最強カードの日付、どんな話が出るのでしょうか。