素数大富豪が8121013倍強くなりたい

素数大富豪の攻略・布教活動をしていきます

n枚2n桁を2のべき乗でできるだけたくさん割りたい話

あけましておめでとうございます。OTTYです。この記事は素数大富豪 Advent Calendar 2021 - Adventarの10日目の記事です。
2022年のアドベントカレンダー書こうと思ったら2021年のを書いていないことに気づきました。
大変遅くなり申し訳ございません。

はじめに

来たる2022/12/4(日)にはち杯にて合成数出しのみの特殊ルールでの試合(通称:合成数大富豪)が行われます。
やばいですね。どのような試合になるのか、きちんとゲームとして成り立つのか、とても気になるところですね。
僕も大会に向け真面目に準備しております。普段の素数大富豪とは色々違った立ち回りが求められそうです。

このルールでの戦略は色々考察しているのですが、それらは後日語ることにします。
今回は合成数大富豪にむけて合成数探索していたら見つけた、あるn枚2n桁の性質の話をしようと思います。役に立つかは知りません。

テーマは2のべき乗です。
n枚2n桁で2^m*R(Rは奇数。合成数でもよい)という形でmが割と大きくて使いやすい合成数を探していました。
そんな中で、任意のnに対して2^2nを約数に持つn枚2n桁があるという事実を何かに活かせないかなーと考えました。
意外と使える可能性あるのではと思ったので共有しておきます。あと単純に事実として面白いし。

2^2nを約数に持つn枚2n桁について

考えたことなかったのですが、「2^2nを約数に持つn枚2n桁」はどのnに対しても1つ存在します。
例えば、Q=2^2*3やKQ=2^5*41です。(KQのように2^2nよりも大きな2の冪で割れることもある)

そして、その見つけ方も簡単で作りやすいです。

1枚ではQ=2^2*3なので2^2で割れます。
2枚ではQの頭にKをつけてKQ=2^5*41となります。
3枚ではKQの頭にTをつけてTKQとすればTKQ=2^6*1583となり確かに2^6で割れます。
4枚ではTKQの頭にKをつけて、KTKQとすればKTKQ=2^8*3*7*2437となります。2^8で割れることが確認できますね。

このような感じでn枚出しで2^2nで割れるものの頭に札をうまく選んでつければn+1枚出しで2^{2(n+1)}で割れるものを作ることができます。
10^(2k)=2^(2k)*5^(2k)となることと、T,J,Q,Kを4で割った時の余りが2,3,0,1となることから示せるので、一応証明しておきます。トランプは無限にあるとします。

(証明)

 2^{2n}を約数に持つn枚2n桁はどのnに対してもただ1つ存在する・・・(*)

(*)を数学的帰納法で示す。

 N_k 右からk枚目のカードの数字とする。ただし N_k  10,11,12,13のいずれかとする。
 B_n  N_1 ~  N_n を右から並べてできた数、すなわち

 B_n =10^ {2(n-1)} N_n+10^ {2(n-1)-2} N_{n-1}+ ・・・+10^ {2} N_{2}+ N_{1}

とする。

(ⅰ)  n=1 のとき、

 B_1 = N_1 =12=2^{2×1}×3としたとき、またそのときに限り 2^{2×1}を約数に持つ。


(ⅱ)  n=k のとき、(*)が成立していると仮定する。

仮定から B_{k}=2^{2k}rとなる N_1 ~  N_k の組ただ1つ存在する。( rは整数。偶数でもよい)

このとき、 B_{k}の頭に  N_{k+1} をつけて B_{k+1}を作ると、

 B_{k+1}=10^{2((k+1)-1)}N_{k+1}+B_{k}=2^{2k}×5^{2k}N_{k+1}+2^{2k}r=2^{2k}(5^{2k}N_{k+1}+r)

ここで、 5^{2k}N_{k+1}+r 4の倍数となるように N_{k+1} 決めればよい。

 5^{2k}N_{k+1}+r≡N_{k+1}+r   (mod4)

であるので、

 r≡0   (mod4)のとき N_{k+1}=12

 r≡1   (mod4)のとき N_{k+1}=11

 r≡2   (mod4)のとき N_{k+1}=10

 r≡3   (mod4)のとき N_{k+1}=13

とすれば 5^{2k}N_{k+1}+r 4で割り切れるようできる。

よって B_{k+1} N_{k+1} をうまく選ぶことで 2^{2(k+1)}を約数に持つようにでき、また N_{k+1}  rから1つに定まる。

(ⅰ)(ⅱ)から(*)は示された。

(証明終わり)


要するに、上の例のTKQやKTKQみたいなのを続けていけば2^2nで割れるn枚2n桁が得られるし、それは1個しかないよって話です。

5枚なら、KTKQ=2^8*3*7*2437から、3*7*2437≡1(mod4)なので頭にJをつけてJKTKQとすればJKTKQ=2^10*107*10159となります。

6枚なら、JKTKQ=2^10*107*10159から、107*10159≡1(mod4)なのでJをつけてJJKTKQとすればJJKTKQ=2^13*83*163417となります。

同様に7枚、8枚......とずっと続けていくことで......KKQJQKQJKQQQKJJJTJJQTJJKTKQという列が得られます。
調べていけば2^100を約数に持つ50枚100桁を構成できるとか面白いですね。
T,J,Q,Kの4で割った余りがすべて異なることに初めて注目しました。なんてよくできたゲームなんだ。

それが何の役に立つの?

この事実は面白い(と少なくとも僕は思っている)ですが、合成数大富豪で役に立つのでしょうか。
現実的に有効に使えそうなのは贔屓目に見てもJJKTKQまでってところでしょう。
正直7枚出し以上の素因数を見たところ出しやすい合成数はなさそうです。

じゃあ、観賞用かと言うかとそうとも言い切れません。

例えば、4枚出しで何か強めな合成数を探すのに、末尾をTKQにして頭にKではない何かつけてみると少なくとも2^6を約数に持つ4枚7桁、8桁が得られます。
そうすると、5TKQ=2^8*19927、8TKQ=2^6*Q6583、9TKQ=2^K*J*TA、JTKQ=2^7*86729とか現実的に出せそうな合成数が見つかります。

このように頭を挿げ替えて探索してみるのはどうでしょうかと提案してみます。頭につける数の4で割った余りなんかに着目するといいかもしれません。

4枚6桁についても、例えば頭をKQの頭をTではなく、4で割った時余りがTと同じく2になる2桁の78とか94なんてものをつけてみると、78KQ=2^T*7*T9、94KQ=2^8*3677なんかが簡単に見つかります。逆に2^4を約数に持つが2^5を約数に持たないようにしたい*1なら、4で割ったとき余りが1,3であるものをKQの頭につけてみるのもいいかもしれませんね。

そんな感じで、KQやTKQ、KTKQの頭に1枚2枚足して探索してみるとよいものが見つかるかもしれません。さらに、これを応用してJJKTKQとかの長いものから2枚を変えたりしたらいい8枚12桁とかがあるかもしれません。知らんけど。

おわりに

最近、はち杯に向けて6枚出しまでの合成数一覧をつらつらを眺めつつ、良さそうな合成数をツイートすることを日課にしています。
なんかないかなーと探していますが使いやすさと強さを両立する合成数ってなかなかないですよね。


そんななか、ふと思ったことを記事にしてみました。
いままで気にしていなかったn枚2n桁の性質の話でしたが、今回紹介した探索方法なら素数判定機(素因数分解機?)だけでも簡単にできるのではないでしょうか。
n枚2n-1桁やn枚2n-2桁の良さそうな合成数が発見できるかもしれないので、ぜひmy合成数を探索してみてください。いい合成数が見つかったら(僕だけにこっそり)教えください。

それにしても、はち杯楽しみですね。
合成数大富豪はスタートラインがみんなほぼ同じなので、素数大富豪始めたころのワクワク感に近いものを感じています。
僕はまず一人プレイでどうにか上がれるようにするために、素数富豪的に勿体ないと感じる並びでも出しやすい合成数を覚えていこうと思います。

以上、読んでいただきありがとうございました。2021年12/22分のアドベントカレンダーも11月中に埋めるように努力します。

*1:5は素因数として使たいのでありがちな願望