こんにちは。くろこんです。今回は素因数分解を筆算で解く方法についてご紹介します。
実はこの筆算を使ったパズルがプライムクロスナンバーです。興味のある方はどうぞ。
49949 を素因数分解する具体例
| $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | ||
|---|---|---|---|---|---|---|---|---|---|
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | |
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | |
| $2^5$ | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | |
| $2^6$ | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | |
| $2^7$ | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 |
上の表のような数を取捨選択して 49949 を目指すパズル、と考えます。
後半は５桁の整数に対して３桁の整数を法とした mod （整数の余りを計算する演算）を多用する、なかなかに難しい手続きになります。前半部分のそれなりの計算だけを見てもよいと思うので、小休憩ポイントを用意してあります。
大きい数に対応する数を決定する
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | |||||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | |
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | |
| $2^5$ | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | |
| $2^6$ | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | |
| $2^7$ | $1$ | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 |
表に追加された $2^7$ に対応する部分の $1$ は「対応する行や列を残すことを可能にする」ことを表します。厳密にいうと、もし表に $0$ が追加されたら「対応する行や列をすべて破棄する」ことを表します。逆説的に $1$ を追加することは「 $0$ を追加しなかった」ことを表します。
16384 は対応する行も列も $1$ が入力されたので、破棄しないことが確定します。
ここで $1$ を追加する理由を説明します。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | |||||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | |
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | |
| $2^5$ | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | |
| $2^6$ | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | |
| $2^7$ | $0$ |
もし、先ほどの $1$ のどちらかが $0$ になると、要素がいくつか破棄されます。元の表の数の総和は 65025 ですが、破棄された値を引くと 32385 になります。49949 を素因数分解するつもりでしたが、この後すべての値を $1$ にしても 32385 しか値が残りません。値が足りないため、ここで $0$ にするのは間違いで、両方 $1$ にするしかない、ということがわかります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | ||||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | |
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | |
| $2^5$ | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | |
| $2^6$ | $1$ | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 |
8192 |
| $2^7$ | $1$ | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 |
16384 |
次の $2^6$ に対応する部分の値も $1$ になります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | ||||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | |
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | |
| $2^5$ | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | |
| $2^6$ | $0$ | ||||||||
| $2^7$ | $1$ | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 |
16384 |
先ほどと同じ理由で、$1$ のどちらかが $0$ になると、要素がいくつか破棄され、 65025 から破棄された値を引くと 48705 になります。49949 には値が足りないため、$2^6$ に対応する部分も $0$ にするのは間違いで、両方 $1$ にするしかない、ということがわかります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $0$ | $1$ | $1$ | |||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 64 | 128 | ||
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | ||
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 | 64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 | 128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 | 256 | 512 | 1024 | 2048 | 8192 |
16384 |
次の $2^5$ に対応する部分は $1$ と $0$ が正しいとわかります。今のところ入力した数が対称なので、どちらを $1$ にしても計算としては成り立ちます。今回は左側を $1$ にしました。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $0$ | $1$ | $1$ | |||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 64 | 128 | ||
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | ||
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 1024 | 2048 | ||
| $2^5$ | $0$ | ||||||||
| $2^6$ | $1$ | 64 | 128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 | 256 | 512 | 1024 | 2048 | 8192 |
16384 |
$2^5$ に対応する部分を両方 $0$ にすると、65025 から破棄された値を引いて 49729 になります。残った数では、絶対に 49949 に到達しないことがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | $1$ | |||||||
| $2^0$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | |
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | |
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | |
| $2^5$ | $1$ | 32 | 64 | 128 | 256 | 512 | 1024 |
2048 |
4096 |
| $2^6$ | $1$ | 64 | 128 | 256 | 512 | 1024 | 2048 |
4096 |
8192 |
| $2^7$ | $1$ | 128 | 256 | 512 | 1024 | 2048 | 4096 |
8192 |
16384 |
$2^5$ に対応する部分を両方 $1$ にすると、右下の破棄されないことが確定した値の和を計算すると、50176 になります。今後すべての値を破棄しても、49949 を超えることが確定します。従って、$2^5$ に対応する部分を両方 $1$ にはならず、片方が $1$ 片方が $0$ であることがわかります。
これ以降の値は今までと同じロジックでは値が決定しません。次のステップへと進みます。
小さい数に対応する数を決定する
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | $1$ | $1$ | ||||||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | ||
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
素因数分解する対象の数は奇数です。いずれの因数も奇数になります。$2^0$ に対応する部分は $1$ である必要があります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $0$ | $1$ | $1$ | |||||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | 4 | 8 | 16 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
$2^1$ に対応する部分がいずれも $a$ となっています。これは $2^1$ に対応する部分の値が等しいことを表します。
$2^1$ に対応する部分の値が等しいことは $49949 = 1\pmod{4}$ であることからわかります。表の中の値で、1 と 2 以外の値はすべて 4 で割り切れます。従って、4 で割った余りに影響するのは 1 と 2 の残り方だけに依存して、他の数字は無視できます。
4 で割った余りが 1 となるには、1 が奇数個残り、 2 は偶数個残る場合です。そのような残り方は、$2^1$ に対応する部分が等しい場合のみであることが分かります。$a$ の部分の値が異なる場合に正しくならないことを確認していきます。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | $0$ | $1$ | $1$ | |||||
| $2^0$ | $1$ | 1 |
4 | 8 | 16 | 64 |
128 |
||
| $2^1$ | $1$ | 2 |
8 | 16 | 32 | 128 |
256 |
||
| $2^2$ | 4 | 16 | 32 | 64 | 256 | 512 | |||
| $2^3$ | 8 | 32 | 64 | 128 | 512 | 1024 | |||
| $2^4$ | 16 | 64 | 128 | 256 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
128 | 256 | 512 | 2048 |
4096 |
||
| $2^6$ | $1$ | 64 |
256 | 512 | 1024 | 4096 |
8192 |
||
| $2^7$ | $1$ | 128 |
512 | 1024 | 2048 | 8192 |
16384 |
先ほど $2^1$ に対応する部分を $a$ としましたが、これは $2^1$ に対応する部分を異なる値とした失敗例です。
表に破棄されないことが確定した 2 が１つだけあるため、残りの数字をどのように選択しても、表の値の総和は 4 で割ったときに 3 余る数字を表します。$49949 = 1\pmod{4}$ であることから、表の値の総和が 49949 に一致しなくなってしまいます。
一方で、$2^1$ に対応する部分の値が等しい場合、2 は両方破棄されるか、もしくは両方破棄されないかのどちらかになります。そのため、$a$ という文字を使って、値が等しいことを表現した、ということです。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $0$ | $1$ | $1$ | ||||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
$2^2$ に対応する部分は $b$ と $\bar{b}$ となっています。これは $2^2$ に対応する部分の値が異なることを表します。
$2^2$ に対応する部分の値が異なることは、先ほどと似たような考え方で $49949 = 5\pmod{8}$ であることからわかります。表の中の値で、1 と 2 と 4 以外の値はすべて 8 で割り切れるので、それらの残り方を考えます。
| $a=0$の場合 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | $\bar{b}$ | $0$ | $1$ | $1$ | ||||
| $2^0$ | $1$ | 1 |
4 | 8 | 16 | 64 |
128 |
||
| $2^1$ | $0$ | ||||||||
| $2^2$ | $b$ | 4 | 32 | 64 | 256 | 512 | |||
| $2^3$ | 8 | 32 | 64 | 128 | 512 | 1024 | |||
| $2^4$ | 16 | 64 | 128 | 256 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
128 | 256 | 512 | 2048 |
4096 |
||
| $2^6$ | $1$ | 64 |
256 | 512 | 1024 | 4096 |
8192 |
||
| $2^7$ | $1$ | 128 |
512 | 1024 | 2048 | 8192 |
16384 |
8 で割った余りが 5 となるのは、4 が奇数個残る場合です。$a=0$ の場合、表のように太字の 4 の部分が未確定の値となります。しかし、$b$ と $\bar{b}$ の値は異なるので、必ずどちらか１個の 4 が残ります。そのため、$49949 = 5\pmod{8}$ という条件と矛盾しないことがわかります。
| $a=1$の場合 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | $\bar{b}$ | $0$ | $1$ | $1$ | ||||
| $2^0$ | $1$ | 1 |
2 |
4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $1$ | 2 |
4 |
8 | 16 | 32 | 128 |
256 |
|
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | 16 | 32 | 64 | 128 | 256 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 |
128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 |
256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 |
512 | 1024 | 2048 | 8192 |
16384 |
$a=1$ の場合、表のように太字の 4 の部分が未確定の値となります。また、$2^2$ に対応する 2 2 4 の３つは破棄されないことが確定します。合計で $4+(2+2+4)=12$ が破棄されないことになりますが、8 で割った結果は 4 になり、左上にある 1 と合わせて 8 で割った余りが 5 であることを表します。そのため、$49949 = 5\pmod{8}$ という条件と矛盾しないことがわかります。
そのため、$2^2$ に対応する部分は、4 を奇数個残すことを考えると、値が異なる場必要があり、 $b$ と $\bar{b}$ として異なる値を表現しています。
総合的な制約から数を決定する
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $\bar{d}$ | $0$ | $1$ | $1$ | |||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
$2^4$ に対応する部分は $d$ と $\bar{d}$ となっています。これは、大きい数に対応する数を決定するときと同じように、$1$ と $1$ や、 $0$ と $0$ を当てはめたときに値の過不足が起こることがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $1$ | $0$ | $1$ | $1$ | |||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 |
64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | ||
| $2^4$ | $1$ | 16 |
32 | 64 | 128 | 256 |
1024 |
2048 |
|
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 |
2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 |
4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 |
8192 |
16384 |
$2^4$ に対応する部分が両方 $1$ の場合、破棄されないことが確定した値の和が 50369 になり、 49949 を超えてしまうことがわかります。先ほどとは異なり、$2^0$ に対応する部分が $1$ に確定することで、破棄されないことが確定した値が多くなっているためです。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $0$ | $0$ | $1$ | $1$ | |||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 64 |
128 |
||
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 128 | 256 | ||
| $2^2$ | $b$ | 4 | 8 | 32 | 256 | 512 | |||
| $2^3$ | 8 | 16 | 32 | 64 | 512 | 1024 | |||
| $2^4$ | $0$ | ||||||||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 2048 |
4096 |
||
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 4096 |
8192 |
||
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 8192 |
16384 |
$2^4$ に対応する部分が両方 $0$ の場合、破棄された値を 65025 から引くと 49457 となり、49949 より小さくなってしまうことがわかります。
$2^5$ に対応する部分では、対称性があることを理由に片方の値を $1$ でもう片方の値を $0$ と決定しましたが、$2^4$ に対応する部分では、すでの今までの決定した値に対称性が無いため、どちらが $1$ にも $0$ にもなりうることから、$d$ と $\bar{d}$ と値を表します。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $\bar{c}$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $c$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | |
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
$2^3$ に対応する部分は $c$ と $\bar{c}$ となっています。今までと同じように確認することでわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $1$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 |
16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $1$ | 8 |
16 | 32 | 64 | 128 | 512 |
1024 |
|
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 |
512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 |
1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 |
2048 | 8192 |
16384 |
$2^3$ に対応する部分を両方 $1$ とすると、破棄されないことが確定した値の和が 46769 になります。また、$d$ と $\bar{d}$ で値が異なるので、$2^4$ に対応する部分の 1024 と 2048 (表で太字にしている部分)の片方は破棄されないことが確定します。$b$ と $\bar{b}$ も同様に、$2^2$ に対応する部分の 256 と 512 (表で太字にしている部分)の片方は破棄されないことが確定します。この分を足すと、破棄されないことが確定した値の和は 50609 となり、49949 を超えてしまうことがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $0$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 16 | 64 |
128 |
||
| $2^1$ | $a$ | 2 | 4 | 8 | 32 | 128 | 256 | ||
| $2^2$ | $b$ | 4 | 8 | 64 | 256 | 512 | |||
| $2^3$ | $0$ | ||||||||
| $2^4$ | $d$ | 16 | 32 | 64 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
64 | 128 | 512 | 2048 |
4096 |
||
| $2^6$ | $1$ | 64 |
128 | 256 | 1024 | 4096 |
8192 |
||
| $2^7$ | $1$ | 128 |
256 | 512 | 2048 | 8192 |
16384 |
$2^3$ に対応する部分を両方 $0$ とすると、65025 から破棄された値を引くと 52833 になります。また、$d$ と $\bar{d}$ で値が異なるので、$2^4$ に対応する部分の 1024 と 2048 (表で太字にしている部分)の片方は破棄されることが確定します。$b$ と $\bar{b}$ も同様に、$2^2$ に対応する部分の 256 と 512 (表で太字にしている部分)の片方は破棄されることが確定します。この分を合わせて引くと 48993 となり、49949 より小さくなることがわかります。
小休憩
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $\bar{c}$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $c$ | 8 | 16 | 32 | 64 | 128 | 512 | 1024 | |
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
これは既にほぼ因数分解ができている状態です。$111dcba1$ という二進数と、$110 \bar{d} \bar{c} \bar{b} a 1$ という二進数が因数分解の結果です。$a$ $b$ $c$ $d$ のいずれも $0$ か $1$ の値となるので、１６回試せば因数分解ができています。もしくは 49949 が因数分解できない数字の場合、すべての場合で因数分解ができないという結果が得られます。
ここから先は大変な計算になりますが、まぁ $a$ $b$ $c$ $d$ を１６回試せばいいか、と飛ばしてもよいです。
総合的な制約から数を決定する 上級編
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $b$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $\bar{b}$ | 8 | 16 | 32 | 128 | 512 | 1024 | ||
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
$49949 = 29\pmod{64}$ であることから、32 の残り個数は偶数の必要があります。左下の 32 は破棄されないことが確定しているので、他の破棄されない 32 の個数は奇数の必要があります。この場合、$b=\bar{c}$ とするとよいことがわかります。
$2^2$ の部分と $2^3$ の部分に注目すると、すべて $b$ か $\bar{b}$ のいずれかの値となっているため、32 が１つ残ることがわかります。
ここで $a$ で場合分けを行います。
| $a=0$の場合 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | $\bar{b}$ | $b$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
4 | 8 | 16 | 64 |
128 |
||
| $2^1$ | $0$ | ||||||||
| $2^2$ | $b$ | 4 | 32 | 64 | 256 | 512 | |||
| $2^3$ | $\bar{b}$ | 8 | 32 | 128 | 512 | 1024 | |||
| $2^4$ | $d$ | 16 | 64 | 128 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
128 | 256 | 512 | 2048 |
4096 |
||
| $2^6$ | $1$ | 64 |
256 | 512 | 1024 | 4096 |
8192 |
||
| $2^7$ | $1$ | 128 |
512 | 1024 | 2048 | 8192 |
16384 |
$a=0$の場合、32 は他に残りません。また、4 も 8 も 16 もそれぞれ１つずつしか残らないことが分かります。
$49949 = 29\pmod{64}$ の条件と矛盾しないことがわかります。
| $a=1$の場合 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | $\bar{b}$ | $b$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 |
4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $1$ | 2 |
4 |
8 | 16 | 32 | 128 |
256 |
|
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $\bar{b}$ | 8 | 16 | 32 | 128 | 512 | 1024 | ||
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 |
128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 |
256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 |
512 | 1024 | 2048 | 8192 |
16384 |
$a=1$の場合、$a=0$ の場合と比べて、新たに 2 2 4 が残り、8 16 32 がさらに１つずつ残ります。ただし、新たに残った値を足すと、64 になるため、$a=0$ と同様に、$49949 = 29\pmod{64}$ の条件と矛盾しないことがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $\bar{b}$ | $\bar{d}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 64 | 256 | 512 | |||
| $2^3$ | $b$ | 8 | 16 | 128 | 512 | 1024 | |||
| $2^4$ | $d$ | 16 | 32 | 64 | 128 | 1024 | 2048 | ||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
一方で、$b=c$ とした場合を考えたとき、$2^2$ の部分と $2^3$ の部分に注目すると、32 がすべて破棄されることがわかります。先ほどと同様に、$a$ について場合分けすると、この残りの 32 の個数が奇数となることから、あまりが 61 であることが示されますが、$49949 = 29\pmod{64}$ と矛盾することがわかります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $b$ | $b$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $\bar{b}$ | 8 | 16 | 32 | 512 | 1024 | |||
| $2^4$ | $\bar{b}$ | 16 | 32 | 64 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
同様に $49949 = 29\pmod{128}$ であることを考えます。 64 の残り個数も偶数の必要があります。この場合、$b=\bar{d}$ とするとよいことがわかります。
| $a=0$の場合 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $0$ | $\bar{b}$ | $b$ | $b$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
4 | 8 | 16 | 64 |
128 |
||
| $2^1$ | $0$ | ||||||||
| $2^2$ | $b$ | 4 | 32 | 64 | 256 | 512 | |||
| $2^3$ | $\bar{b}$ | 8 | 32 | 512 | 1024 | ||||
| $2^4$ | $\bar{b}$ | 16 | 64 | 1024 | 2048 | ||||
| $2^5$ | $1$ | 32 |
128 | 256 | 512 | 2048 |
4096 |
||
| $2^6$ | $1$ | 64 |
256 | 512 | 1024 | 4096 |
8192 |
||
| $2^7$ | $1$ | 128 |
512 | 1024 | 2048 | 8192 |
16384 |
先ほどと同様に考えると $a=0$ の場合、32 が合計で２つ、64 は３つ残ります。$49949 = 29\pmod{128}$ の条件と矛盾しないことがわかります。
| $a=1$の場合 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | $\bar{b}$ | $b$ | $b$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 |
4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $1$ | 2 |
4 |
8 | 16 | 32 | 128 |
256 |
|
| $2^2$ | $b$ | 4 | 8 | 32 | 64 | 256 | 512 | ||
| $2^3$ | $\bar{b}$ | 8 | 16 | 32 | 512 | 1024 | |||
| $2^4$ | $\bar{b}$ | 16 | 32 | 64 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
64 |
128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 |
256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 |
512 | 1024 | 2048 | 8192 |
16384 |
$a=1$の場合、$a=0$ の場合と比べて、新たに 2 2 4 8 16 32 64 が１つずつ残ります（64 は $2^1$ と $2^5$ の部分です）。新たに残った値を足すと 128 になるため、この場合も $49949 = 29\pmod{128}$ の条件と矛盾しないことがわかります。
| 失敗例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $\bar{b}$ | $b$ | $\bar{b}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 16 | 32 | 128 | 256 | |
| $2^2$ | $b$ | 4 | 8 | 32 | 256 | 512 | |||
| $2^3$ | $\bar{b}$ | 8 | 16 | 32 | 128 | 512 | 1024 | ||
| $2^4$ | $b$ | 16 | 32 | 128 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
一方で、$b=d$ とした場合を考えたとき、$2^2$ の部分と $2^4$ の部分に注目すると、64 がすべて破棄されることがわかります。先ほどと同様に、$a$ について場合分けすると、この残りの 64 の個数が奇数となることから、あまりが 93 であることが示されますが、$49949 = 29\pmod{128}$ と矛盾することがわかります。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $a$ | $a$ | $\bar{a}$ | $\bar{a}$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 | 4 | 8 | 16 | 64 |
128 |
|
| $2^1$ | $a$ | 2 | 4 | 8 | 128 | 256 | |||
| $2^2$ | $\bar{a}$ | 4 | 32 | 64 | 256 | 512 | |||
| $2^3$ | $a$ | 8 | 16 | 32 | 512 | 1024 | |||
| $2^4$ | $a$ | 16 | 32 | 64 | 1024 | 2048 | |||
| $2^5$ | $1$ | 32 |
64 | 128 | 256 | 512 | 2048 |
4096 |
|
| $2^6$ | $1$ | 64 |
128 | 256 | 512 | 1024 | 4096 |
8192 |
|
| $2^7$ | $1$ | 128 |
256 | 512 | 1024 | 2048 | 8192 |
16384 |
同様に $49949 = 29\pmod{256}$ であることを考えます。 128 の残り個数も偶数の必要があります。この場合、$a=\bar{b}$ とするとよいことがわかります。
残りの変数が１つしかないので $49949 = 285\pmod{512}$ であることも同時に確認します。
| よい例 | $2^0$ | $2^1$ | $2^2$ | $2^3$ | $2^4$ | $2^5$ | $2^6$ | $2^7$ | |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $1$ | $1$ | ||
| $2^0$ | $1$ | 1 |
2 |
4 |
64 |
128 |
|||
| $2^1$ | $1$ | 2 |
4 |
8 |
128 |
256 |
|||
| $2^2$ | $0$ | ||||||||
| $2^3$ | $1$ | 8 |
16 |
32 |
512 |
1024 |
|||
| $2^4$ | $1$ | 16 |
32 |
64 |
1024 |
2048 |
|||
| $2^5$ | $1$ | 32 |
64 |
128 |
2048 |
4096 |
|||
| $2^6$ | $1$ | 64 |
128 |
256 |
4096 |
8192 |
|||
| $2^7$ | $1$ | 128 |
256 |
512 |
8192 |
16384 |
$a=\bar{b}$ として、かつ $a=1$ とした場合を考えます。
64 以下の数字をすべて足すと、$29+128+256 = 413$ となります。128 の残りが５個、256 の残りが３個であることを合わせると、128 は合計で６個分で、$49949 = 29\pmod{256}$ と矛盾しないことがわかります。256 は、128 の６個分から 256 の３個分として加わって合計７個あり、$49949 = 285\pmod{512}$ と矛盾しないことがわかります。
ここで計算した $1$ と $0$ の列、$11111011$ と $11000111$ はそれぞれ二進数で 251 と 199 を表し、いずれも素数なので 49949 の素因数分解は $251 \times 199 = 49949$ とわかります。
数学的視点
上記のパズルは、数学でいう分枝限定法を素因数分解に当てはめた方法となります。全探索しないといけないところを、いろいろと条件を使って枝狩りしています。
分枝限定すればいいので、例えば、三進数でも、もっとめちゃくちゃな構造の数でもいいのですが、いったん二進数にしています。
今回は 49949 を８桁の二進数で割れることを仮定して、8x8 の表でパズルをしましたが、これは本質的には問題はないです。１桁×１５桁、２桁×１４桁、……とすべて試せばいい、ということですが、パズルとして取り組む場合にそれは厳しすぎるので桁数は予め設定するのが無難です。
なかなか大変な内容でしたが、今回はこの辺りで。