HNC入門
この記事は、 素数大富豪 Advent Calendar 2022 - Adventarの22日目の記事です。
昨日の記事はまだありません。
一昨日の記事はマモさんによる、時間についてでした。
プレイヤーとしても、大会運営者としても、とても興味深い内容でした!
1. HNCとは
HNCとは、"Hello New Composite Number!" の略で、合成数に出会うことを指します。
そんなこと可能なのか?と思われる方もいるかもしれませんが、「等式は正しいが使用している素因数が素数かどうか分からない合成数出し」 をして合成数出しが成功すれば合成数に出会ったことになります。なので、HNCは素因数に出会っているということもできます。
(覚えていない合成数出しをその場で作っても、その合成数出しが正しいことが出す前に分かっている場合は、 ある意味合成数に出会ってはいますが、これをHNCと呼ぶことはないです。)
(理論上、「使用している素因数が素数であることは知っているが等式が成り立つかわからない合成数出し」 に出会うのもHNCと言えますが、確率が低すぎるので無視します。)
今回は主に、$ N=2*P $ という形の合成数出しの作り方を解説していきます。
2. きっかけ
私が素数大富豪を始めたばかりのころ、周りの強い方との知識の差に悩まされていました。 私は覚えるのがあまり得意ではないので、知識の差を他の所でカバーできないかと考えました。 そこで、「合成数をその場で作る」という方法を思いつき、考察を始めました。 考察をするうちに、合成数出しの「トランプを使って式を作る」というパズル的な側面に惹かれ、合成数出しについて色々研究するようになりました。
3. 凡例
本記事では以下の記号を使います。
- $ATJQKX$ 以外のアルファベット : カード列
- $(大文字アルファベット)_n$ : (高々)n桁のカード列
- $NM$ : NとMを結合したもの
本題に入る前に作るのが簡単な合成数を紹介します。
4. 10の倍数
1番簡単な合成数出しです。
$ N=2*5*P $ という形で書けますが、$N$の末尾には基本的に$T$を使うため、$P$の末尾は$A$か$J$になります。
なので、
- $NT=2*5*NA$
- $NAT=2*5*NJ$
という形が一般的です。
5. 繰り返し
同じ数字を繰り返すのも計算がしやすくて便利です。(同じ札をたくさん使う点に注意)
5.1 周期1
- $P_1 P_1 = J*P_1$
- $P_1 P_1 P_1 = 111*P_1 = 3*37*P_1$
- $P_1 P_1 P_1 P_1 = 1111*P_1 = J*TA*P_1$
- etc.
5.2 周期2以上
- $P_2 P_2 = TA*P_2$
- $P_3 P_3 = 1001*P_3 = 7*J*K*P_3$
- $P_4 P_4 = 10001*P_4 = 73*137*P_4$
- etc.
他にもたくさんありますが割愛します。
6. 例題
それでは本題に...と行きたいところですが、最初にいった通り$N=2*P$という合成数出しにはパズル的な面白さがあります。 なので、これから書く解説はある意味「パズルのネタバレ」的な要素が含まれます。 ネタバレされたくない方は、以下の例題を解いてから先に進んでください。 (例題ではパズルとして成立させるために、解は1つしかありません。また、素数判定は13以下の倍数判定のみで十分になるように作問しました。)
- "$ 21248 $"
- "$ 21347 $"
- "$ 2112389 $"
- "$ 2357789 $"
- "$ 21244577 $"
- "$ 2467K $"
- "$ 22457Q $"
- "$ 2445679K $"
- "$ 21225TT $"
- "$ 2235566TJQ $"
下にスクロールすると解法があります。
7. 解法
以下、
- $P=p_a p_{a-1} ... p_1 p_0$
- $N=n_a n_{a-1} ... n_1 n_0$
- $p_i$と$n_i$の桁数は等しい
とします。
($p_i, n_i$ は枚数の少ないカード列だと思ってください)
($P_n$と紛らわしいですがこれ以降$P_n$は使わないのでご了承ください。良い表記があれば教えていただけると嬉しいです。)
7.1 基本解法
$p_0,n_0,p_1,n_1,...,p_i,n_i,...$
の順でカードを決めていくことで合成数出しを作ることが出来ます。
例)例題2
$p_0=7$とすると、$n_0=4$となります。
$p_1=1$とすると、1の位から繰り上がりがあるため$n_1=3$となります。
以上より、$34=2*17$を作ることが出来ました!。
これが分かれば$N=2*P$の形の合成数出しはできるので、練習してみてほしいです。
素数大富豪オンラインで練習する場合は、下の画像のようにカードを並べると分かりやすいと思います。$(X=2)$
私もこの並べ方を使っています。
※素数大富豪オンラインでは、「等式は正しいけど合成数出し失敗」のとき「~を出しましたが、~は素因数ではありません」というメッセージが出ます。
7.2 実戦的な解法
基本解法だけだと戦略としてこの合成数出しをするのは難しいので、以下のような考え方で合成数を作るスピードを速くします。
7.2.1 1桁札のみの場合
$p_i,n_i$が1桁のとき、数の組 $ (p_i, n_i) $ は以下の20通りしかありません.
$ (p_i, n_i)= $
$ (0,0),(0,1),(1,2),(1,3), $
$ (2,4),(2,5),(3,6),(3,7), $
$ (4,8),(4,9),(5,0),(5,1), $
$ (6,2),(6,3),(7,4),(7,5), $
$ (8,6),(8,7),(9,8),(9,9) $
また、下の桁からの繰り上がり、上の桁への繰り上がりの有無で分類すると、
下から | 上へ | ||||||
---|---|---|---|---|---|---|---|
$ I $ | 無 | 無 | $ (0,0) $ | $ (1,2) $ | $ (2,4) $ | $ (3,6) $ | $ (4,8) $ |
$ II $ | 有 | 無 | $ (0,1) $ | $ (1,3) $ | $ (2,5) $ | $ (3,7) $ | $ (4,9) $ |
$ III $ | 無 | 有 | $ (5,0) $ | $ (6,2) $ | $ (7,4) $ | $ (8,6) $ | $ (9,8) $ |
$ IV $ | 有 | 有 | $ (5,1) $ | $ (6,3) $ | $ (7,5) $ | $ (8,7) $ | $ (9,9) $ |
となります。また、下からの繰り上がりがある $ (p_i, n_i) $ の個数と上への繰り上がりがある $ (p_i, n_i) $ の個数は等しいので、
- $ II $ と $ III $ は同じ個数
- $ IV $ が1個以上あるとき、 $ II, III $ も1個以上必要
であることが分かります。
以上の条件を満たすように手札をいくつかの2枚のカードの組に分けることが出来れば、$ N=2*P $ の形の等式を作ることが出来ます。
絵札がある場合も考え方はほぼ同じで、$ p_i,n_i $ が2桁以上の場合を考えればよいです。
7.2.2 $ p_i,n_i $ が2桁のとき
$ (p_i, n_i)=(10,?),(11,?),(12,?),(13,?),(?,10),(?,11),(?,12),(?,13), $
これはそれぞれの組に2つずつの解があり、
$ (p_i, n_i)= $
$ (10,20),(10,21),(11,22),(11,23), $
$ (12,24),(12,25),(13,26),(13,27), $
$ (05,10),(55,10),(05,11),(55,11), $
$ (06,12),(56,12),(06,13),(56,13), $
となります。これを1桁札と同様に4つに分類すると、
下から | 上へ | |||||||
---|---|---|---|---|---|---|---|---|
$ I $ | 無 | 無 | $ (10,20) $ | $ (11,22) $ | $ (12,24) $ | $ (13,26) $ | $ (05,10) $ | $ (06,12) $ |
$ II $ | 有 | 無 | $ (10,21) $ | $ (11,23) $ | $ (12,25) $ | $ (13,27) $ | $ (05,11) $ | $ (06,13) $ |
$ III $ | 無 | 有 | $ (55,10) $ | $ (56,12) $ | ||||
$ IV $ | 有 | 有 | $ (55,11) $ | $ (56,13) $ |
となります。
7.2.3 $p_i,n_i$ が3桁以上のとき
3桁以上で考える必要があるものは以下の4つのみです。
下から | 上へ | |||
---|---|---|---|---|
$ I $ | 無 | 無 | $ (105,210) $ | $ (106,212) $ |
$ II $ | 有 | 無 | $ (105,211) $ | $ (106,213) $ |
これらで考えるべきものが網羅できていることの確認は演習問題とします。
8. 実戦例
1. まず2をどけます。
2. 絵札が2枚あるので、$(p_i,n_i) = (T6,2K)$とします。
3. $p_0$の候補が9しかないので、$(p_0,n_0)=(9,8)$とします。
4. 残り4枚の分け方は(5,1),(4,8)しかありません。
5. 順番を並び替えます。繰り上がりの有無から、
- $(5,1)$は$(T6,2K)$と$(9,8)$の間に入る。
- $(4,8)$は末尾には来ない。
となるので、
$(p_0,n_0,p_1,n_1,p_2,n_2,p_3,n_3)=(9,8,5,1,T6,2K,4,8)$
となります。
6. 通常の並べ方に戻して出します。
9. おわりに
大会でのHNCを私以外がやっているところを見たことがないので、HNCが出る試合を観戦できることを楽しみにしています。
明日以降の記事は全く埋まっていません!書いてくれる方をお待ちしています。