最大素数大富豪合成数の探索について
この記事は素数大富豪 Advent Calendar 2020 - Adventarの16日目の記事です。
昨日はマモさんの5枚、5枚、57の出す順について - まもめもでした。
最近いろんな戦術の記事があって、どれも面白いですよね！
先日、発見されている中で最大の素数大富豪合成数の大きさを更新したので、
今までに発見されたもののまとめと、今後の進展について書こうと思います。
・ルールの確認
念のため、合成数出しのルールを確認しておきます。
・出したい合成数を場に出し、その素因数分解の式を素因数場に出す。
このとき、
1. 演算子は、掛け算 " * " と冪乗 " ^ " の2つを使うことができる。
2. カッコ " ( ) " は使えない。
3. N = 1*p, N = p^0 のように、素因数場では0と1を単体で使うことはできない。
・正しい例
6 = 2*3
8 = 2^3
18 = 2*3^2
5Q = 2^3^2 (a^b^c と書いた場合、a^(b^c) と同じ意味です)
・間違っている例(ペナルティを受けるもの)
6 = 2*5 (等式が間違っている)
Q = 3*4 (素因数分解になっていない)
・間違っている例(出せないもの)
6 = 1*2*3 (1を単体で使っている)
6 = 2*3*5^0 (0を単体で使っている)
5 = 5 (素因数場が2つ以上の正整数の積、冪乗であらわされていない)
36 = (2*3)^2 (カッコは使えない)
64 = (2^2)^3 (カッコは使えない)
見つかっている合成数の中からいくつかピックアップして紹介しようと思います。
99887766544332KKQQJJQATTT
=2*5*99887766544332KKQQJJA2ATTA
(35桁, XY = QT, 余り : 5)
発見日 : 2018/07/28
発見者 : onewanさん (参照ツイート)
比較的探索しやすい N=2*5*P の形の合成数。
冪乗を使わない形の合成数出しの中では最大に近いと思われます。
53A69J983K966349A6A522824AQK78304
=2^Q2
(37桁, XY = 20, 余り : 4557778TTTTJJJQQKK)
冪乗を使えば掛け算しか使わない合成数出しより大きくできそうだと思い、
2の冪乗を全部調べ、発見しました。
(特にツイートはしなかったので、第一発見者は不明)
24666899776A76599Q22473Q83245A53K48AJ
=J*K*A7*QK^Q
(41桁, XY = 67, 余り : 358TTTTJJK)
発見日 : 2020/07/03
発見者 : nishimuraさん (参照ツイート)
QK^Q*N の形の合成数出しを探索して見つけたとのこと。
A7752356T465Q3KTAK596AK849J73Q25947T4A
=3^8*20K89^8
発見日 : 2020/08/07
発見者 : はち (参照ツイート)
(47桁, XY = 50, 余り : 26TJJJQQ)
素因数場で使う数字の桁数(枚数ではない)の合計が小さいほうから全探索し発見しました。
素因数場が合計10桁以下の合成数の中で最大。
※この合成数の素因数場の桁数は9桁。
・探索方法
素因数場で使う数字の桁数の合計が小さいほうから全探索しました。
全探索以外の方法で見つけても、それが最大であることを証明するためには結局全探索が必要になるというのが主な理由です。
トランプ1デッキは joker を絵札として使うと 54枚72桁なので、
素因数場で d 桁使ったとき、合成数は (72-d) 桁以下になります。
47桁の合成数が見つかっているので、
72-d >= 47 となる、
d <= 25 について全探索することができれば、
最大の合成数を見つけることができます。
※実戦で出すことのできない54枚消費の合成数も含めて探索しています。
・計算量
「素因数場25桁以下の合成数を全探索すれば最大合成数が見つかる」
と書きましたが、何個の合成数を計算する必要があると思いますか？
とりあえず、出せないものや同じカードを7枚以上使うものも含めてざっくり計算してみましょう。
素因数場が決まれば合成数も決まるので、素因数場の並びだけ考えます。
素因数場がd桁のとき、数字の並べ方は 10^d 通りです。
演算子 " * ", " ^ " の入る位置は d-1個あって、それぞれの位置について、
(1) "*" が入る
(2) "^" が入る
(3) なにも入らない
の3通りがあるので、演算子の並べ方は 3^(d-1) 通りです。
以上より、素因数場がd桁の合成数は
10^d*3^(d-1) = (30^d)/3 通りあります。
なので、d <= 25 について全探索しようとすると、
Σ(2 <= d <= 25) (30^d)/3
= (30^26-30^2)/(30-1)/3
≈ 2.9*10^36 [個]
計算する必要があります。
1つの合成数の計算にかかる時間を 10^(-8) [秒/個] としても、
2.9*10^36 [個] * 10^(-8) [秒/個]
= 2.9*10^28 [秒]
≈ 9.3*10^20 [年] (= 9.3垓年)
かかることになります。
※10^(-8) [秒/個] は、一般的なコンピュータが1回の簡単な四則演算を行うのにかかる時間。
・計算量を減らすためにしたこと
愚直にすべて計算していたら時間がかかりすぎるので、計算量を減らす方法を考えました。
・小さすぎるものや大きすぎるものを省く
すでに見つかっている合成数よりも小さいものや、
73桁以上の大きすぎる合成数の計算を省略する。
・同じ計算を省く
掛け算の順序を入れ替えただけの組み合わせを省いたり、
冪乗しか使わない式をあらかじめ計算しておいたりすることで、
複数回同じ計算をしないようにする。
この方法で素因数場10桁以下の全探索はできました。
(11桁も2週間くらいかければ計算できると思うのですが、メモリが足りなくなる恐れがあるのでまだやってません。)
・さらに効率化するにはどうしたらよいか
最大合成数を見つけるにはまだまだ効率化が必要です。
そのために私が考えている案は、
・計算の省略ができるところを探す。
まだ同じ計算をしている部分はあるので、そこを修正する。
・とても大きい合成数を見つける。
1つ大きいのが見つかれば探索範囲が小さくなるので、探索時間が短縮できる。
・合成数の上限を小さくできるような法則を見つける。
現状「1デッキで作れる」以外に上限を定めるものがないので、
他の方法で上限を小さくできれば、探索範囲を小さくできる。
しかし、合成数の数字の並びの数学的な性質を考えないといけないのでかなり難しい。
・スパコンを借りる。
ただ、これだけでは大きく計算量を減らすことはできないので、今までとは違う探索方法を見つけないといけないかもしれないです。
・おわりに
正直、最大素数大富豪合成数を見つけるのはかなり難しいと思います。
ですが、探す人がたくさんいれば見つかる確率も上がると思うので、
この記事を読んで興味を持ってくれた方は是非自分で探索してみてほしいです。
明日はなきゃのさんによる、大会の解説についての記事です。
マスプライム杯の解説はとても分かりやすかったので楽しみですね！
