こんにちは。くろこんです。今回は素因数分解を筆算で解く方法についてご紹介します。
前回 49949 の素因数分解を実質的に分枝限定法で解く方法を紹介しました。
しかし、あまりにも凶悪な難易度のため、今回はイージーモードとして 143 を素因数分解する内容を書きたいと思います。大きい値に挑戦したい方は、上記の記事をおすすめです。
素因数分解の筆算を使ったパズル
これもおまけ要素としてリンクを載せておきます。
143 を素因数分解する具体例
| $2^0$ | $2^1$ | $2^2$ | $2^3$ | ||
|---|---|---|---|---|---|
| $2^0$ | 1 | 2 | 4 | 8 | |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | 4 | 8 | 16 | 32 | |
| $2^3$ | 8 | 16 | 32 | 64 |
上の表のような数を取捨選択して 143 を目指すパズルと考えます。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | |||||
| $2^0$ | 1 | 2 | 4 | 8 | |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | 4 | 8 | 16 | 32 | |
| $2^3$ | $1$ | 8 | 16 | 32 | 64 |
表に追加された $2^3$ に対応する部分の $1$ が追加されました。もし表に $0$ が追加されたら対応する行や列をすべて破棄することを表します。逆説的に $1$ を追加することは $0$ を追加しなかった ことを表します。
64 は対応する行も列も $1$ が入力されたので、$0$ が追加されて破棄されるということがないので、破棄しないことが確定します。表の数字の周りが囲まれているのは、破棄しないことが確定していることを表します。（通常の行列の考え方に沿って、横を行、縦を列として扱っています）
取捨選択して 143 を目指すというのは破棄しないことが確定した値の和を 143 にするということになります。表の値の総和は 225 なので、言い換えると破棄する値の和を 82 にするということにもなります。
ここで $1$ を追加する理由を説明します。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | |||||
| $2^0$ | 1 | 2 | 4 | 8 | |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | 4 | 8 | 16 | 32 | |
| $2^3$ | $0$ |
もし、先ほどの $1$ のどちらかが $0$ になると、要素がいくつか破棄されます。表の取り消し線の値は、破棄されたことを表します。
$0$ にした場合、破棄された値の和は 105 になり、目標とした破棄する値の和 82 を超えます。今後どのように表の値を定めても、破棄した値は必ず 82 を超える（ 105 以上になる）ため、ここで $0$ にするのは間違いであることがわかります。
従って、64 に対応する行も列も両方 $1$ にするしかないとなります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | $1$ | ||||
| $2^0$ | 1 | 2 | 4 | 8 | |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | $0$ | ||||
| $2^3$ | $1$ | 8 | 16 | 32 | 64 |
次の $2^2$ に対応する部分の値は片方が $1$ 片方が $0$ にするしかないことがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $0$ | $1$ | ||||
| $2^0$ | 1 | 2 | 8 | ||
| $2^1$ | 2 | 4 | 16 | ||
| $2^2$ | $0$ | ||||
| $2^3$ | $1$ | 8 | 16 | 64 |
次の $2^2$ に対応する部分の両方が $0$ だとすると、破棄する値の和は 104 になり 82 を超えます。そのため、少なくとも片方は $1$ にしないといけないことがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | $1$ | ||||
| $2^0$ | 1 | 2 | 4 | 8 | |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | $1$ | 4 | 8 | 16 |
32 |
| $2^3$ | $1$ | 8 | 16 | 32 |
64 |
次の $2^2$ に対応する部分の両方が $1$ だとしたとき、右下の破棄されない値の和に注目します。その和は 144 となり、143 を超えます。つまり、残りすべての行と列の値をどのようにしても（例えすべて $0$ としても）、必ず 143 を超えてしまうため、少なくとも片方は $0$ にしないといけないことがわかります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | $1$ | ||||
| $2^0$ | 1 | 2 | 4 | 8 | |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | $0$ | ||||
| $2^3$ | $1$ | 8 | 16 | 32 | 64 |
以上のことから、 $2^2$ に対応する部分の値は片方が $1$ 片方が $0$ にするしかないことがわかります。今のところ対称性から、どちらが $1$ でも $0$ でも計算はできるため、列のほうを $1$ としました。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | $1$ | $1$ | |||
| $2^0$ | $1$ | 1 |
2 | 4 |
8 |
| $2^1$ | 2 | 4 | 8 | 16 | |
| $2^2$ | $0$ | ||||
| $2^3$ | $1$ | 8 |
16 | 32 |
64 |
$2^0$ に対応する部分の値は両方 $1$ にするしかないことがわかります。これは単純に、奇数になっているのは表の左上の 1 がただ１つであるため、143 の素因数分解では破棄しないことが必要条件です。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
4 |
8 |
|
| $2^1$ | $1$ | 2 |
8 |
16 |
|
| $2^2$ | $0$ | ||||
| $2^3$ | $1$ | 8 |
32 |
64 |
最後に $2^1$ に対応する部分の値は、この表のように値を定めるしかないことがわかります。これは単に、表で破棄されないことが確定している値の和が 143 になっていることから定めています。
ここで、表の中で定めた $1$ と $0$ が二進数の素因数分解の結果になっています。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | |
|---|---|---|---|---|---|
| $1$ | $4$ | $8$ | |||
| $2^0$ | $1$ | 1 |
4 |
8 |
|
| $2^1$ | $2$ | 2 |
8 |
16 |
|
| $2^2$ | |||||
| $2^3$ | $8$ | 8 |
32 |
64 |
$1$ を隣接する２の累乗の値に置き換えて、足し算すると、列の方は$1+4+8=13$、行の方は$1+2+8=11$となります。$13 \times 11 = 143$ となるので、素因数分解と一致します。
数学的視点
上記のパズルは、数学でいう分枝限定法を素因数分解に当てはめた方法となります。全探索しないといけないところを、いろいろと条件を使って枝狩りしています。
興味深いのは、例えば、双子素数（差が２の素数ペア）の積は素因数分解が簡単だ というようなことが直感的に現れます。これは上位ビットがおおよそ等しいため、行と列の $0$ と $1$ の値の対称性が長い間保たれるということになります。
一方で、下位ビットでは反転ビットのペアが続く場合に素因数分解が簡単だという性質が現れます。これも先ほどの双子素数の積の場合に当てはまります。これは、mod 演算などを使って素因数分解の整合性を出すときに行か列の片方だけが破棄されるということを有効に使えるからです。
今回はこのあたりとなります。お読みいただきありがとうございます。