コラッツ予想の証明
の収束
ウィキペディア「コラッツの問題」より
任意の正の整数 n に対して、以下で定められる操作について考える。
- n が偶数の場合、n を 2 で割る
- n が奇数の場合、n に 3 をかけて 1 を足す
このとき、「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。
コラッツの問題における終了状態の確認と、その証明の条件と言われている2点の方法を示す。
終了状態の確認
1.値が循環しないこと
2.値が拡散しないこと
この時点で、16は2の4乗なので終了するのが分かる。2進数にすると
となる。これによって、2進数の01の2桁がいくつか並んだ値が1に収束する状態であると分かる。すぐ後に示すように、それ以外の場合はない。以後、特に断りのない限り数式内の数値は2進数とし、括弧内を10進数(例「1001(9)」)、カンマの後の数字は3の剰余数(例「1011(11,2)」)とする。
奇数の演算1回で1に収束しない例:
2つの1が隣接している場合
これらは偶数を2で割ることに実質的な意味はなく、2進数で見た時の1の値の最上位桁と最下位桁が一つになった状態「2の乗数」になるということである。
つまり「奇数の演算 を繰り返すと必ず2の乗数になる」というのがコラッツの問題の本質である。ただし3を掛けた後に加えるのは1ではなく、2進数値での1の値の最小位桁と同じ値であること。
演算結果が3を法として0と合同になることはない。これは奇数の演算結果 では必ず3を法として1と合同となるのだから、その数の因数に3が無いことによる。
【値が循環しない理由】
個別の演算ごとに値が循環しないこと
仮に値が循環するとして、それは以下に挙げた3種類ある演算のどれを行った時か。
まず で循環するとして、初めの演算をする値を
、その演算後の値を
、循環する値を
、その演算後の循環した値を
とすれば
![]()
(a)
(b)
![]()
となり と矛盾する。これは演算前の値があることを想定したのだが、演算前の値のない初期値ではどうか。
だが演算前の値がない初期値というのは3の倍数であり、演算後に3の倍数は現れないのだから同じ値になることもない。 も
と同様に矛盾する結果になるのは明らか。
しかし は指数に差が出ることにより演算後に等しくなる可能性がある。事実、以下のように7から数回の演算を行った後に29あるいは117となった場合、偶数の演算で同じ値となってしまうが、実際の連続する演算ではあり得るか。
このように奇数の演算後に上位桁の0と1の並びが等しく下位0の数だけが異なるというのは、初期値3の倍数から始めて1になるまでの演算の中に現れることはなく、それは初期値である3の倍数を別の値で始めた場合の合流点に当る。したがって の演算でも循環することはない。
複数の演算による値の循環がないこと
値が循環するということは、演算を繰り返して1に収束されるまでに、それらの値が現れないということである。
上位桁に1があるとして、以下のように最下位桁に連続で演算を施すと、取りこぼしなく、すべての桁が有効であるのが分かる(桁を固定するために偶数の演算 を省略し、奇数の演算における+1は逆に
を行なう)。
もし有効ではない桁があれば、それによって1に収束しないものもあり得る。それは奇数の演算を変形した の場合、最下位桁を削除することにより起こる。
この演算で1に収束する数をみていくと最小値が3、第2位が11であり、その間の5,7,9は1に収束せずに循環してしまうが、これは-1により最下位の値が有効にならないためである。5,7は直接,9は13,19,7へと推移して循環する。
【値が拡散しない理由】
値の拡散は演算結果が平均して拡大していくことにより起こる。個々の拡大は奇数の演算による。
2進数値において、最上位よりも最下位桁の伸び率の方が十分に高いこと
最終的に1に収束するというのは、奇数の演算だけを行った場合、2進数での最下位桁の1が最上位桁の1に追い付くということである(ここでは青の1が赤の1に)。
通常の演算 奇数だけの演算 最上位と最下位桁の開き![]()
![]()
![]()
![]()
![]()
![]()
2進数での最上位桁は3倍になるのだから安定した状態では 桁の伸びである。最下位桁の伸びである末尾の0は+1により確実に1桁はあり、隣接する上位桁が0であれば桁上げにより2となる。
2桁の伸び
1桁の伸び
であり、隣接する上位桁が0の場合と同じく2桁の伸びとなる。したがって最上位桁と最下位桁の伸びの比率は である。これは収束するには十分な比率であり、無限の値でなければ最後は1に収束する。
7を例にした最上位桁と最下位桁の伸びの推移
演算回数 | 通常の演算 | 奇数だけの演算 | 桁の伸び数 | |||
最上位桁 | 最下位桁 | |||||
0 | 111 | 7 | 111 | 7 | 0 | 0 |
1 | 1011 | 11 | 10110 | 22 | 2 | 1 |
2 | 10001 | 17 | 1000100 | 68 | 4 | 2 |
3 | 1101 | 13 | 11010000 | 208 | 5 | 4 |
4 | 101 | 5 | 1010000000 | 640 | 7 | 7 |
5 | 1 | 1 | 100000000000 | 2048 | 9 | 11 |
最上位桁の伸び率(1.8)=桁の伸び数(9) /演算回数(5)
最下位桁の伸び率(2.2)=桁の伸び数(11)/演算回数(5)
伸び率比(0.818) =最上位桁の伸び率(1.8)/最下位桁の伸び率(2.2)
上位桁と最下位桁の伸び率比(値のみ2進数)
種別 | 値/桁数 | 演算回数 | 最上位桁 | 最下位桁 | 伸び率比 (最上位桁/最下位桁) |
||
桁数 | 伸び率 | 桁数 | 伸び率 | ||||
0 | 11(3) | 2 | 4 | 2 | 5 | 2.5 | 0.8 |
0 | 101(5) | 1 | 2 | 2 | 5 | 5 | 0.4 |
0 | 111(7) | 5 | 9 | 1.8 | 11 | 2.2 | 0.818 |
0 | 1001(9) | 6 | 10 | 1.667 | 13 | 2.167 | 0.769 |
0 | 1011(11) | 4 | 7 | 1.75 | 10 | 2.5 | 0.7 |
1 | 101 | 528 | 838 | 1.587 | 938 | 1.777 | 0.893 |
2 | 101 | 210 | 334 | 1.590 | 434 | 2.067 | 0.769 |
3 | 101 | 268 | 427 | 1.593 | 527 | 1.966 | 0.810 |
1 | 1001 | 4923 | 7805 | 1.585 | 8805 | 1.789 | 0.886 |
2 | 1001 | 2417 | 3832 | 1.585 | 4832 | 1.999 | 0.793 |
3 | 1001 | 2621 | 4156 | 1.586 | 5156 | 1.967 | 0.806 |
1 | 10001 | 48126 | 76280 | 1.585 | 86280 | 1.793 | 0.884 |
2 | 10001 | 24131 | 38248 | 1.585 | 48248 | 1.999 | 0.793 |
3 | 10001 | 24300 | 38546 | 1.586 | 48546 | 1.998 | 0.794 |
- 0: 値
- 1: 111...111
- 2: 100...001
- 3: 1<乱数>1
値が拡大する状態の判定 の演算結果が奇数になるのは3を法として2と合同な数の最大値であり、この場合のみ偶数演算を施しても拡大する。これは演算前の値の最下位2桁が11の場合に限るが、それは以下の理由による。
11より1大きい数100の3倍は3を法として0と合同となる …………(a)
11を3倍して1を加えると3を法として1と合同となる………………(b)
両者を加えると2で割ることができ、かつ2で割ると奇数になる………(c)
以上の演算結果は3を法として2と合同となる……………………………(d)
(a)
(b)
(c)
(d)
2進数100の3倍が3を法として0と合同となるのだから、下2桁が00の2進数の3倍は必ず3を法として0と合同となる。
したがって、すべての奇数は下2桁が11であれば演算により3を法として2と合同な数の最大値となる。
拡大する状態が有限であること
上位桁に連続する1がある状態で3倍する場合、下2桁は常に01、上2桁が10となり中間は1で詰まる。これは下位からの桁上げがないことと上位の1が途絶えることによる。
最下位桁に連続する1がある場合は1を加える事により、連続する1は演算前より1桁少ない値となる。つまりこれらの状態で演算を繰り返すと、連続する1の桁数分だけ値が拡大し、その後収束することになる。
したがって、拡大は演算前の値における最下位桁の連続する1によるが、連続する1が有限個であればいずれ収束する。
2連続で拡大した後に縮小する例:
発生、消滅を繰り返す場合、拡大の伸び率よりも縮小の伸び率の方が十分に高いこと
拡大できる状態である最下位桁11の値の小さいものを見ると
11(3,0) は3の倍数であるからこれを発生できない。
111(7,1)は1001(9,0)により発生する。
9も3の倍数であるからこれを発生できないが、隣接する上位桁に2進数10を追加することによりこれを回避でき、かつ発生させる11の数を同じ桁数だけ増やすことができる。
発生する値を拡大する条件(最下位桁の連続する1が3桁以上、2桁ずつ)
拡大する値を発生する条件(最下位桁が01で隣接する上位桁に1つ以上の10)
拡大する値を発生する条件と、桁を減らす01の並んだ条件は3桁以降の0と1の順番が逆の値であり、これらを生成する確率は等しいと言える。しかし拡大/縮小の演算ではその回数が異なり、拡大(拡大桁数)>縮小(1)である。
縮小拡大
![]()
![]()
![]()
![]()
![]()
![]()
それぞれの最上位桁と最下位桁との伸び率は、初期値の桁数をTと置くと拡大の演算回数が となり
縮小の演算![]()
![]()
![]()
拡大の演算
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
拡大した値での最上位桁の伸び率は正確ではないが としての計算値は
であるが実際の演算では8未満となる。そこで最上位桁の伸びを8とすると、縮小した値との比は1:4となり、拡大する値の発生、拡大を繰り返しても最終的に収束することになる。さらに演算数の少ない縮小には、演算回数の差である(拡大(T-1)-縮小(1) = (T-2))により
を比率とした縮小が加わるのである。
桁数T=114として演算を行なうと、以下の結果が得られる。縮小の方は常に1回の演算を行なうだけなので桁数が増えれば差も広がるのである。
縮小する状態 初期値(桁数114) 010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 演算結果-縮小の終了 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 演算回数1回 拡大し続ける状態 初期値(桁数114) 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001 演算結果-拡大の終了(桁数293、最下位桁179) 10110111000000110100000101010111100111010000101001010001011101110100101110111110111001100111100010000110000011010010010101101100001000010001100011100111000110100110110010110000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 演算回数113回
なお、 のような他の状態でも拡大する値は得られるが、1の密度が高くなる(
)ことにより無駄な値や桁が発生してしまい、拡大効率(拡大回数/初期値の桁数)は悪くなる。
以上から
演算 を繰り返しても循環することはなく、拡散することもない
∴コラッツの予想は正しい