こんにちは。くろこんです。今回は素因数分解を使ったパズルを創って、その作り方が大変だというお話です。難しいために今回の記事を読み切っても、プライムクロスナンバーは作れるようにならないかもしれません。ご了承ください。
プライムクロスナンバーとは
素因数分解を使ったパズルで、8x8 の表に収まるように数字を因数分解します。例えば、問題は下記のように与えられます。
←8x8 8299 20550 32274
↑8x8 9017 19359
こちらに解き方を紹介しています。結果は猫のようなドット絵が現れます。
プライムクロスナンバー新作
こちらは新作のパズルです。例題と同じように解くことができるので、ご興味のある方はどうぞ。
←8x8 33782
↑8x8 23835 33673 39039 53295
←8x8 9943
↑8x8 8001 20805 34008 56355
←8x8 23807 38745
↑8x8 1055 46937 64260
プライムクロスナンバーを作るときに気にすること
ここからは、理論的側面に触れていきます。まず、パズルとして存在する個数の上限を考えます。例えば、先ほどの例題であれば、
←8x8 8299 20550 32274
↑8x8 9017 19359
のように、現れる整数は 8 ビット整数 < 256 の数を因数に持つので、必ず 255*255 = 65025 より小さくなります。
従って、←矢印に $2^{65025}$ 通り、↑矢印に $2^{65025}$ 通りの数字の選び方があり、少なくとも $2^{130050}$ よりは個数が少ないです。全部確認すればいいですね！（無理）
プライムクロスナンバーを作るときに気にすること １段階踏み込み
もう少し踏み込んで考えてみます。8299 = 193 x 43、20550 = 150 x 137 のように、因数分解の仕方が１通りになるなるような数字が選択されるため、実際には 65025 よりも選択可能な数字は少ないです。
8299 = 43 * 193
20550 = 2 * 3 * 5 * 5 * 137 = 137 * 150
選択可能な数字というのは、20550 のように素数２つだけの積ではない、8x8 という条件だからこそ１通りになるような数字を含みます。
20550 の例では、素数である 137 を因数に持ちますが、137 x 2 = 274 で 2 倍以上すると 256 以上になってしまう数のため、片方の因数が 137 で確定してしまいます。そのため、8x8 に収まるような因数分解の仕方は、20550 = 137 x 150 以外にないことがわかります。
地道にパソコンで検索すると、10621 個の自然数が条件を満たすことがわかります。0 は真っ黒な絵を表し、あっても意味がない数字なので、自然数の範囲で選択可能な数字は数えています。
従って、少なくとも $2^{21242}$ よりは個数が少ないです。まだまだ大変です……。
プライムクロスナンバーを作るときに気にすること ２段階踏み込み
ちょっと考え方を変えてみます。$2^{21242}$ のパターンには、10000 個の自然数によるプライムクロスナンバーが含まれます。
$$
\quad_{21242} C_5 \quad < 2^{70} << \quad_{21242} C_{100} \quad << \quad_{21242} C_{10621}
$$
二項定理を使って考えると、含まれるプライムクロスナンバーのほとんどは 100 個以上、1000 個以上の整数で表されます。それらの存在個数は指数関数的に増えていきます。
整数 5 個の問題どころか、整数 100 個の問題すら少数派で、そのほとんどは整数 10621 個付近の問題となっています。ほとんどは整数が多すぎて人間に解くことが難しい問題になっているのです。
例えば、5 個の整数になるように問題を作りたいのであれば、10621 のなかから 5 個を選択して、絵が完成するか確認します。これなら、${}_{21242} C_5 < 2^{70}$ の確認で済みます。（これでも結構つらいですが……）
プライムクロスナンバーを無理やり作る
先ほどの考え方は、5 個の整数からなる華麗なプライムクロスナンバーを作るときの考え方でした。
実際には、絵に対応する整数の最小個数は 5 個ではないこともあります。そのため、いくら確認しても絵が出来上がらないことがあります。
今度は、たくさんの整数をつなげてもいいので、絵を完成させることを考えます。以下のような整数の組み合わせを考えます。
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
これらの XOR を取ったものに、さらに 255 x 255 を合わせることで、１ドットだけ白い絵ができます。
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
つまり、このような１ドットの数字の組み合わせを複数用意しておくことで、ドットを操作するように絵を完成することができます。
プライムクロスナンバーを無理やり作る １段階踏み込み
先ほどの組み合わせて絵を作るときに、実は合成規則があります。
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
今度は２行目２列目の部分の１ドットの数字の組み合わせです。先ほどのパターンと合わせて、合成することを考えます。
←8x8 64516 64770 65025
↑8x8 64770
←8x8 64009 64515 65025
↑8x8 64515
この２つを合成します。上が１行目１列目の部分の１ドット、下が２行目２列目の部分の１ドットを表します。 64770 = 254 x 255 と 64515 = 253 x 255 に注目します。
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
それぞれのマスで 1 の出現回数が偶数か奇数か、を考えるのが XOR なので、上の表のように、254 x 255 XOR 253 x 255 と 252 x 255 XOR 255 x 255 は全く同じになることがわかります。これは、縦横が違っても同じ考え方ができます。
0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
従って、これらを合わせると次のようになります。
←8x8 64516 64770 65025
↑8x8 64770
←8x8 64009 64515 65025
↑8x8 64515
↓
←8x8 64009 64516 64515 64770 65025 65025
↑8x8 64515 64770
↓
←8x8 64009 64516 64260 65025 65025 65025
↑8x8 64260 65025
ここでやはり XOR は 1 の出現回数が偶数か奇数かを考えるので、同じ数字が２回出現していれば削除できます。また、平方数は対称性から ←8x8 と ↑8x8 のどちらにも移動できます。従って、上に出現している 65025 はすべて削除することができます。
←8x8 64516 64770 65025
↑8x8 64770
←8x8 64009 64515 65025
↑8x8 64515
↓
←8x8 64009 64516 64260
↑8x8 64260
以上のことから、合成をすることができました。注目するべきポイントは、通常の整数、左側の因数が255の整数、上側の因数が255の整数の３通りに分割して考えることで合成が可能になるということです。
それでも難しいプライムクロスナンバーの作成
以上を踏まえて、無理やりプライムクロスナンバーを大量に作成し、せいぜい$2^{70}$よりは少ないだろうから根性でいいものを探し出すというのが基本のアプローチです。
高校以降で習う行列を使うと、いくつかの演算を効率化できるためそのような工夫はしますが、せいぜいそのくらいしかせずに気合で問題を作成し、整数の個数を減らすのに成功したのが冒頭の新作です。
そのため、整数 8 個以上でないと表現できない複雑な図形などでは、PC の処理が現実的な時間で終わりません。9 個以上とかはかなり絶望的です。
版権などがあるので無尽蔵には作りづらいのもあり、何かいいパズルはないかなと模索中でもあります。いいアイデアないかな～。
それでは、今回はここまでとなります。チャレンジしてもらって、いい方法などあれば、教えてもらえると嬉しいです。