インテジャーズ

インテジャーズ

数、特に整数に関する記事。

99998888777766665555444433332222131313131313121212121111111011010101111:最大素数大富豪素数

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

発見者: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

どうでもよいですが、5371も素数ですね!

概要

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

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

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

まず、

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

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

9(4枚)
8(4枚)
7(4枚)
6(4枚)
5(4枚)
4(4枚)
3(4枚)
2(4枚)
K(4枚)
・ジョーカー(2枚)
Q(4枚)
J(3枚)
10(1枚)
A(1枚)
10(3枚)
J(1枚)
A(2枚)

最大であることの証明

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

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

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

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

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

記号

  • \mathbb{P}_{\text{Daifugo}}^{(d, k)}を「k枚のカードを用いて出来るd桁の素数大富豪素数全体」とする。
  • \begin{equation}\begin{split}N := &999988887777666655554444333322221313131313131212121211111\\ &11011010101111 \in \mathbb{P}_{\text{Diafugo}}^{(71, 53)} \end{split}\end{equation}

(最後の"\in"はNが素数と仮定することによって分かる)。

  • 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|で表す。
  • ジョーカーを2枚用いて出す素数大富豪素数nに対して、J_n(a, b)でジョーカー2枚を何のカードの代わりとして用いているかを表す(a, b \in \mathrm{Cards} \cup \{ 0 \})。一般にはJ_n(a, b)nに対して一意には定まらない付加構造である。
  • n \in \mathbb{P}_{\text{Daifugo}}^{(d, 53)}に対して、nを手札に持つプレイヤーとは異なるもう一人のプレイヤーの手札にあるカード(それは一枚である)をR_nと表す。

仮定(P)が成立し、その結果N=Mであることの証明.
n \in \mathbb{P}_{\text{Daifugo}}^{(d, k)}に付加構造J_n(a, b)が付随していると仮定する。このとき、

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

である。従って、J_M(a, b)に対して、\left|a\right|, \left|b\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_M(a, b)=J_M(K, K)を示せばよい。これは

N^{(44)} = 99998888777766665555444433332222131313131313

であることから、J_M(a, b) \neq J_M(K, K)と仮定すると

M^{(44)} \neq 99998888777766665555444433332222131313131313

となるため、N < MとなってMの定義に矛盾する。すなわち、Mの付加構造はJ_M(K, K), R_M=Aであり、Peria氏の計算(およびtsujimotter氏による追試)によってN=Mが確定する。 Q.E.D.

素因数分解

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

\displaystyle 99998888777766665555444433332222131313131313121212121111111011010101111

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

ポイント

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

解決者ご本人様による記事:

qiita.com

今後の課題としてはPeria氏の記事にも書かれている通り、「最大素数大富豪合成数」のサーチです。こちらは合成数出しのルールから、(直観では)素数の場合に比べて難易度がはるかに高い気がします。また、一人で遊べる「素数大富豪アプリ」の開発が待たれます(恐らくAIを作る部分が一番面倒)。