　こんにちは。くろこんです。今回は素因数分解を使ったパズルを作ったので紹介します。

プライムクロスナンバーとは

　素因数分解を使ったパズルで、8x8 の表に収まるように数字を因数分解します。例えば、問題は下記のように与えられます。

←8x8 8342 20550 32274
↑8x8 9017 19359

　まず、左上の 8342 に注目します。因数分解すると 193 × 43 なので

8342 = 193 x 43

   1の位        128の位
    1 1 0 1 0 1 0 0

1   1 1 0 1 0 1 0 0   1の位
0   0 0 0 0 0 0 0 0   2
0   0 0 0 0 0 0 0 0   4
0   0 0 0 0 0 0 0 0   8
0   0 0 0 0 0 0 0 0   16
0   0 0 0 0 0 0 0 0   32
1   1 1 0 1 0 1 0 0   64
1   1 1 0 1 0 1 0 0   128の位

のような表にします。193 と 43 のそれぞれを二進数で表して、表の縦横に対応させます。193 は二進数で 11000001 で、43 は二進数で 00101011 です。１の位が左上に対応するように数字を当てはめます。ここで、8342 に関しては矢印が左を向いているので、左側の数字（横に対応する数字）が大きくなるように表を作ります。

　表の数字は、整数を表す左端の０１列か上端の０１列の数字が０なら０になるようにします。表の数字で１になっているのは、左端も上端も数字が１になっていることを表します。左端と上端の掛け算の結果が表の値となっている、ということもできます。

　次に、20550 も同じように考えます。

20550 = 150 x 137

    1 0 0 1 0 0 0 1

0   0 0 0 0 0 0 0 0
1   1 0 0 1 0 0 0 1
1   1 0 0 1 0 0 0 1
0   0 0 0 0 0 0 0 0
1   1 0 0 1 0 0 0 1
0   0 0 0 0 0 0 0 0
0   0 0 0 0 0 0 0 0
1   1 0 0 1 0 0 0 1

　20550 は素因数分解すると 2 × 3 × 5 × 5 × 137 です。ただし、表のサイズが 8x8 という縛りがあるので、どちらの値も 8 桁の二進数で表せる 255 以下であることが必要です。この条件を満たす因数分解の仕方は 150 × 137 しかないことがわかります。150 は二進数で 10010110 で、137 は二進数で 10001001 になります。20550 も矢印が左側なので左側に大きい数字の 150 を当てはめます。

　残りの数字もすべて同じように分解します。

32274 = 198 x 163, 9017 = 71 x 127, 19359 = 81 x 239

    1 1 0 0 0 1 0 1        1 1 1 1 1 1 1 0        1 1 1 1 0 1 1 1

0   0 0 0 0 0 0 0 0    1   1 1 1 1 1 1 1 0    1   1 1 1 1 0 1 1 1
1   1 1 0 0 0 1 0 1    1   1 1 1 1 1 1 1 0    0   0 0 0 0 0 0 0 0
1   1 1 0 0 0 1 0 1    1   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 0    0   0 0 0 0 0 0 0 0    0   0 0 0 0 0 0 0 0
0   0 0 0 0 0 0 0 0    0   0 0 0 0 0 0 0 0    1   1 1 1 1 0 1 1 1
0   0 0 0 0 0 0 0 0    0   0 0 0 0 0 0 0 0    0   0 0 0 0 0 0 0 0
1   1 1 0 0 0 1 0 1    1   1 1 1 1 1 1 1 0    1   1 1 1 1 0 1 1 1
1   1 1 0 0 0 1 0 1    0   0 0 0 0 0 0 0 0    0   0 0 0 0 0 0 0 0

　最後に出来上がった表の XOR をとります。 XOR 演算は偶数か奇数かを判定する演算と同じで、同じマスが奇数回１なら１、偶数回１なら０にします。

8342 XOR 20550

    1 1 0 1 0 1 0 0         1 0 0 1 0 0 0 1

1   1 1 0 1 0 1 0 0     0   0 0 0 0 0 0 0 0     1 1 0 1 0 1 0 0
0   0 0 0 0 0 0 0 0     1   1 0 0 1 0 0 0 1     1 0 0 1 0 0 0 1
0   0 0 0 0 0 0 0 0     1   1 0 0 1 0 0 0 1     1 0 0 1 0 0 0 1
0   0 0 0 0 0 0 0 0 XOR 0   0 0 0 0 0 0 0 0  =  0 0 0 0 0 0 0 0
0   0 0 0 0 0 0 0 0     1   1 0 0 1 0 0 0 1     1 0 0 1 0 0 0 1
0   0 0 0 0 0 0 0 0     0   0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0
1   1 1 0 1 0 1 0 0     0   0 0 0 0 0 0 0 0     1 1 0 1 0 1 0 0
1   1 1 0 1 0 1 0 0     1   1 0 0 1 0 0 0 1     0 1 0 0 0 1 0 1

　５個の表について偶数奇数を判定するので、表を２つずつ逐次判定していっても結果は同じになります。今回の説明では、逐次判定していく方法を採用します。まず、8342 の表と 20550 の表の XOR を計算しました。２つの表の偶数か奇数かを判定するので、表の値が異なれば奇数なので１、表の値が等しいなら偶数なので０、と考えることもできます。以降では、残りの表の XOR も同じように計算していきます。

(8342 XOR 20550) XOR 32274

                        1 1 0 0 0 1 0 1

1 1 0 1 0 1 0 0     0   0 0 0 0 0 0 0 0     1 1 0 1 0 1 0 0
1 0 0 1 0 0 0 1     1   1 1 0 0 0 1 0 1     0 1 0 1 0 1 0 0
1 0 0 1 0 0 0 1     1   1 1 0 0 0 1 0 1     0 1 0 1 0 1 0 0
0 0 0 0 0 0 0 0 XOR 0   0 0 0 0 0 0 0 0  =  0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1     0   0 0 0 0 0 0 0 0     1 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0     0   0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0
1 1 0 1 0 1 0 0     1   1 1 0 0 0 1 0 1     0 0 0 1 0 0 0 1
0 1 0 0 0 1 0 1     1   1 1 0 0 0 1 0 1     1 0 0 0 0 0 0 0

(8342 XOR 20550 XOR 32274) XOR 9017

                        1 1 1 1 1 1 1 0

1 1 0 1 0 1 0 0     1   1 1 1 1 1 1 1 0     0 0 1 0 1 0 1 0
0 1 0 1 0 1 0 0     1   1 1 1 1 1 1 1 0     1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 0     1   1 1 1 1 1 1 1 0     1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 XOR 0   0 0 0 0 0 0 0 0  =  0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1     0   0 0 0 0 0 0 0 0     1 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0     0   0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1     1   1 1 1 1 1 1 1 0     1 1 1 0 1 1 1 1
1 0 0 0 0 0 0 0     0   0 0 0 0 0 0 0 0     1 0 0 0 0 0 0 0

(8342 XOR 20550 XOR 32274 XOR 9017) XOR 19359

                        1 1 1 1 0 1 1 1

0 0 1 0 1 0 1 0     1   1 1 1 1 0 1 1 1     1 1 0 1 1 1 0 1
1 0 1 0 1 0 1 0     0   0 0 0 0 0 0 0 0     1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0     0   0 0 0 0 0 0 0 0     1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 XOR 0   0 0 0 0 0 0 0 0  =  0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1     1   1 1 1 1 0 1 1 1     0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0     0   0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1     1   1 1 1 1 0 1 1 1     0 0 0 1 1 0 0 0
1 0 0 0 0 0 0 0     0   0 0 0 0 0 0 0 0     1 0 0 0 0 0 0 0

　さて、ここで出てきた結果の 0 を黒いドット、1 を白いドットに置き換えます。

　猫の顏のようなものが浮かび上がってくるのがわかるでしょうか？

　このように整数のリストから、素因数分解して画像を復元するのがプライムクロスナンバーです。

数学的な視点

　プライムクロスナンバーを解くのは簡単（数学的な意味です。少なくとも、手作業でもできるので……）です。しかし、作るのはとても難しいです。ＮＰ完全性などをチェックしたわけではありませんが、基本的には候補を絞って適切な組み合わせかチェックしていく分枝限定法のようなやり方しかない、と思っています。

余談

　何かパズル化するとよいドット絵などがあればチャレンジしていきます。Ｘの方には、いくつかチャレンジしたものをアップロードしています。