最大素数大富豪素数

最大素数大富豪素数が発見されました。

発見者：Peria氏
発見日：2016年2月22日
最大素数大富豪素数： $99998888777766665555444433332222131313131313121212121111111011010101111$
使用カード枚数：53枚
桁数：71桁
公開ソースコード：Check if the largest prime number in Prime-Daifugo can have 71 digits? · GitHub
追試コード (by tsujimotter氏)：https://gist.github.com/junpeitsuji/db6fa47878c39c0429e9

どうでもよいですが、 $53$ も $71$ も素数ですね！

概要

素数大富豪については $71$ 日前に書いた
integers.hatenablog.com
を参照してください。

素数大富豪素数とは素数大富豪で出すことが可能な素数のことを言います(tsujimotter)。
「最大の素数大富豪素数は何か？」という問題は１年半ほどの間解答がありませんでした。

今回Peria氏によって報告された素数は素数大富豪において次のような状況で出すことができます。

まず、

・プレイヤー人数は２人
・片方が手札が１枚になるまで場にカードを出した後、半永久的にパスし続ける。
・もう一人のプレイヤーが山札のカードを全て引く

なる状況によって手札のカードの枚数を53枚にすることができることに注意します。そうして、今回の候補数は実際に53枚のカードを利用して作ることができます(残るカードはA一枚)。桁の大きい方から考えると次のように並びます：

・ $9$ （４枚）
・ $8$ （４枚）
・ $7$ （４枚）
・ $6$ （４枚）
・ $5$ （４枚）
・ $4$ （４枚）
・ $3$ （４枚）
・ $2$ （４枚）
・ $K$ （４枚）
・ジョーカー（２枚）
・ $Q$ （４枚）
・ $J$ （３枚）
・ $10$ （１枚）
・ $A$ （１枚）
・ $10$ （３枚）
・ $J$ （１枚）
・ $A$ （２枚）

最大であることの証明

Peria氏が発見した数( $N$ とおく)は

仮定(P)：最大素数大富豪素数はジョーカー二枚が両方ともKであり、他のプレイヤーの手札に残っている一枚がＡのときに実現する。

という仮定に基づく最大の素数大富豪素数です。ただし、コードにmpz_probab_prime_pという関数を用いているため、厳密には"おそらく素数"ということしか判定できません。すなわち、以下の議論で得られる結果は厳密には「 $N$ より大きい数は素数大富豪素数にはなり得ず、 $N$ が素数であることが確定すれば $N$ が確かに最大素数大富豪素数を与える」です。しかしながら、 $N$ が素数であるかを別個に確認すればよく、 $N$ は実際に素数であることが確認できます(「素因数分解」の項を参照してください)。

なお、最初のコードには若干のミスがあることがPeria氏によって指摘され、それを修正した上でPeria氏およびtsujimotter氏によって追試されました。

追試の結果、Peria氏の発見した数に誤りのないことが確認されました。従って、あとは仮定(P)の正当性および $N$ が素数であることを証明すれば最大素数大富豪素数問題は解決ですが、前半は以下のように証明できます：

記号

$\mathbb{P}_{\text{Daifugo}}^{(d, k)}$ を「 $k$ 枚のカードを用いて出来る $d$ 桁の素数大富豪素数全体」とする。

$N := 99998888777766665555444433332222131313131313121212121111111011010101111$
( $N$ が素数と仮定しているので、 $N \in \mathbb{P}_{\text{Diafugo}}^{(71, 53)}$ )

$M$ ：最大素数大富豪素数 $\in \mathbb{P}_{\text{Diafugo}}^{(71, 53)}$ ( $N$ の存在によって属する集合が決まる)。

自然数 $n$ に対して、 $n^{(m)}$ で「 $n$ の上 $m$ 桁」を表す。

$\mathrm{Cards} := \{ A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K \}$

$a \in \mathrm{Cards}$ に対して、そのカードの表す数を $\left|a\right|$ で表す。

ジョーカーを二枚( $J_1$ , $J_2$ とする)用いて出す素数大富豪素数 $n$ に対して、 $J_1(n), J_2(n)$ でジョーカー二枚をそれぞれ何のカードの代わりとして用いているかを表す( $J_1(n), J_2(n) \in \mathrm{Cards} \cup \{ 0\}$ )。一般には $J_1(n), J_2(n)$ は $n$ に対して一意には定まらず、 $n$ の一つの出し方に対して組 $(n, J_1(n), J_2(n))$ が一意に定まることに注意。

$n \in \mathbb{P}_{\text{Daifugo}}^{(d, 53)}$ に対して、 $n$ を手札に持つプレイヤーとは異なるもう一人のプレイヤーの手札にあるカード(それは一枚である)を $R_n$ と表す。

仮定(P)が成立し、その結果 $N=M$ であることの証明

$n \in \mathbb{P}_{\text{Daifugo}}^{(d, k)} , J_1(n)=a, J_2(n)=b$ という条件で $n$ を出すことを考える。このとき、

$\left|a\right| \ \text{or} \ \left|b\right| < 10 \Longrightarrow d < 71$

である。 $M$ がジョーカー二枚を使わない場合 $M\in \mathbb{P}_{\text{Diafugo}}^{(71, 53)}$ にならない。従って、 $M$ を出すには必ずジョーカーを二枚用いる必要があり、 $\left|J_1(M)\right|, \left|J_2(M)\right| \geq 10$ が成り立つ。また、 $a \in \mathrm{Cards}$ に対して

$a \in \{ 10, J, Q, K\} \Longrightarrow \left|a\right|^{(1)}=1$

であることに注意すれば、 $n \in \mathbb{P}_{\text{Daifugo}}^{(71, 53)}$ に対して

$n^{(32)} \neq 99998888777766665555444433332222 \Longrightarrow n < N$

が成り立つ。よって、 $M^{(32)}=99998888777766665555444433332222$ であることが従う。これから、 $R_M \neq 2, 3, 4, 5, 6, 7, 8, 9$ である。もし、 $\left|R_M\right|$ が二桁の数ならば、 $M$ の桁数が $71$ 桁未満となって矛盾する( $71$ 桁を実現するためには絶対値が二桁のカードを全て用いる必要がある)。これで $R_M=A$ が示された。あとは必ず $J_1(M)=J_2(M)=K$ であることを示せばよい。これは

$N^{(44)} = 99998888777766665555444433332222131313131313$

であることから、 $J_1(M)$ or $J_2(M) \neq K$ と仮定すると

$M^{(44)} \neq 99998888777766665555444433332222131313131313$

となるため、 $N < M$ となって $M$ の定義に矛盾する。すなわち、 $M$ の出し方は必ず $J_1(M)=J_2(M), R_M=A$ を満たし、Peria氏の計算(およびtsujimotter氏による追試)によって $N=M$ が確定する。 Q.E.D.

素因数分解

あとは $N$ が素数であることを確定させればOKです。次のWeb上で使える楕円曲線法を用いた素因数分解アプリがおすすめです。
www.alpertron.com.ar
これは確率論的判定法だけでなく、厳密な素因数分解まで最終的には与えてくれます。桁数が大きすぎると当然時間がかかることになりますが、 $100$ 桁の数であっても、それが実際に素数であるならば、２秒もかからずに素数であると確定します。そうして、今考えている $N$ が素数であることも一瞬で確定します。
f:id:integers:20160223010151p:plain
以上をもって、Peria氏が発見した

$\displaystyle 99998888777766665555444433332222131313131313121212121111111011010101111$

が最大素数大富豪素数であることが確定しました。

ポイント

Peria氏による発見のポイントは"全ての素数大富豪素数を探索しようとはしない"という点です。仮定(P)を仮定することによって圧倒的に探索すべき数の範囲が狭まります。また、仮定(P)を満たす数もたくさんあるのですが、候補数を大きい順に素数判定にかけていくため、比較的大きい数が素数であればサーチはすぐに終わることになります。つまり、理論的には上手くいかない可能性がある部分が二か所あるのですが(仮定(P)を満たす素数が一切なかったり、あったとしてもサーチのかなり後の方に出現するかもしれない)、結果論として、短いコードで一瞬で見つかるところに" $N$ はいた"のです。もちろん、素数定理等を用いた理論的考察によって、予めこの方法が高確率で上手くいくことを保証できたかもしれませんが、そんなことをするよりも先に手を(コンピュータを)動かして、うまくいかなそうであればそれはそのとき考えるというスタンスでよいと思います。実際には上手くいったので、この部分の考察は不要です。 $N$ がいい形で発見されたことによって、仮定(P)の正当性は容易に証明されました。もし、 $N$ がもっともっと小さい数であれば、( $R_M$ が $A$ でない場合を考慮する必要などが生じて)仮定(P)の証明がより難しくなったり、不成立の可能性すらありました。見つかってしまえば、ご本人の言葉を借りれば「やってることは競技系プログラムだと普通のこと」ということです。興味をもつ人が圧倒的に少なかったために発見までに一年以上かかりましたが、とりあえず発見されて嬉しい限りです。