rabbit2202のブログ

コラッツ予想の証明とそれにまつわる記事を書きます

コラッツ予想の証明

 \hspace{20pt}\boldsymbol{log_2 3\hspace{2pt}/\hspace{2pt}2} の収束

ウィキペディアコラッツの問題」より

任意の正の整数 n に対して、以下で定められる操作について考える。

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 3 をかけて 1 を足す

このとき、「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。



コラッツの問題における終了状態の確認と、その証明の条件と言われている2点の方法を示す。

終了状態の確認

1.値が循環しないこと


2.値が拡散しないこと



終了状態の確認

コラッツの問題について、5の演算を行なう。

 \hspace{15pt}5 \times 3 = 15
 \hspace{10pt}15 + 1 = 16


この時点で、16は2の4乗なので終了するのが分かる。2進数にすると

 \hspace{15pt}101 \times 11 = \hspace{5pt}1111
 \hspace{10pt}1111 + \hspace{5pt}1 = 10000


となる。次に収束値である1について、あえて演算を行なうと

 \hspace{15pt}1 \times 11 = \hspace{5pt}11
 \hspace{10pt}11 + \hspace{5pt}1 = 100


となる。これによって、2進数の01の2桁がいくつか並んだ値が1に収束する状態であると分かる。すぐ後に示すように、それ以外の場合はない。以後、特に断りのない限り数式内の数値は2進数とし、括弧内を10進数(例「1001(9)」)、カンマの後の数字は3の剰余数(例「1011(11,2)」)とする。


奇数の演算1回で1に収束しない例:

2つの1が隣接している場合

 \hspace{20pt}11(3) \times 11 = 1001(9)
 \hspace{10pt}1001(9) + \hspace{5pt}1 = 1010(10)


2つの1が2桁離れている場合

 \hspace{15pt}1001(9)\hspace{5pt} \times 11 = 11011(27)
 \hspace{10pt}11011(27) + \hspace{5pt}1 = 11100(28)



奇数の演算1回で1に収束する例:

01を10個並べた場合

 \hspace{10pt}1010101010101010101 \times 11 = \hspace{5pt}11111111111111111111
 \hspace{10pt}1111111111111111111 + \hspace{5pt}1 = 100000000000000000000(2^{20})


これを10進数で演算すると

 \hspace{15pt}349525 \times 3 = 1048575
 \hspace{10pt}1048575 + 1 = 1048576


これらは偶数を2で割ることに実質的な意味はなく、2進数で見た時の1の値の最上位桁と最下位桁が一つになった状態「2の乗数」になるということである。

つまり「奇数の演算  \boldsymbol{N \times 3 + 1} を繰り返すと必ず2の乗数になる」というのがコラッツの問題の本質である。ただし3を掛けた後に加えるのは1ではなく、2進数値での1の値の最小位桁と同じ値であること

演算結果が3を法として0と合同になることはない。これは奇数の演算結果  N \times 3 + 1 では必ず3を法として1と合同となるのだから、その数の因数に3が無いことによる。


【値が循環しない理由】

個別の演算ごとに値が循環しないこと

仮に値が循環するとして、それは以下に挙げた3種類ある演算のどれを行った時か。

 \hspace{10pt}N \times 3
 \hspace{10pt}N + 1
 \hspace{10pt}N\hspace{3pt}/\hspace{4pt}2^{n}


まず  N \times 3 で循環するとして、初めの演算をする値を  N_1、その演算後の値を  M_1、循環する値を  N_2、その演算後の循環した値を  M_2 とすれば

 \hspace{10pt}N_1 \neq N_2
 \hspace{10pt}N_1 \times 3 = M_1 (a)
 \hspace{10pt}N_2 \times 3 = M_2 (b)
 \hspace{10pt}M_1 =  M_2


(a)を(b)に代入すると

 \hspace{10pt}N_2 \times 3 = N_1 \times 3
 \hspace{10pt}N_2 = N_1


となり  \boldsymbol{N_1 \neq N_2} と矛盾する。これは演算前の値があることを想定したのだが、演算前の値のない初期値ではどうか。

だが演算前の値がない初期値というのは3の倍数であり、演算後に3の倍数は現れないのだから同じ値になることもない。 \boldsymbol{N + 1} \boldsymbol{N \times 3} と同様に矛盾する結果になるのは明らか

 \hspace{10pt}N_3 \neq N_4
 \hspace{10pt}N_3 + 1 = M_3
 \hspace{10pt}N_4 + 1 = M_4
 \hspace{10pt}M_3 =  M_4
 \hspace{10pt}N_4 + 1  = N_3 + 1
 \hspace{10pt}N_4 = N_3


 \boldsymbol{N / 2^{n}} も指数が等しければ矛盾となる

 \hspace{10pt}N_5 \neq N_6
 \hspace{10pt}N_5 / 2^{n} = M_5
 \hspace{10pt}N_6 / 2^{n} = M_6
 \hspace{10pt}M_5 =  M_6
 \hspace{10pt}N_6 / 2^{n}  = N_5 / 2^{n}
 \hspace{10pt}N_6 = N_5


しかし  N / 2^{n} は指数に差が出ることにより演算後に等しくなる可能性がある。事実、以下のように7から数回の演算を行った後に29あるいは117となった場合、偶数の演算で同じ値となってしまうが、実際の連続する演算ではあり得るか。

 \hspace{30pt}111(7)  \hspace{10pt}\times 11 + 1 =    \hspace{20pt}10110,    \hspace{20pt}10110 / 10(2)   \hspace{15pt}= 1011(11)
 \hspace{20pt}11101(29)\hspace{5pt} \times 11 + 1 =  \hspace{10pt}1011000,  \hspace{10pt}1011000 / 10^{11}(2^{3}) \hspace{3pt}= 1011(11)
 \hspace{10pt}1110101(117) \times 11 + 1 = 101100000, 101100000 / 10^{101}(2^{5}) = 1011(11)


このように奇数の演算後に上位桁の0と1の並びが等しく下位0の数だけが異なるというのは、初期値3の倍数から始めて1になるまでの演算の中に現れることはなく、それは初期値である3の倍数を別の値で始めた場合の合流点に当る。したがって  \boldsymbol{N \times 2^{n}} の演算でも循環することはない



複数の演算による値の循環がないこと

値が循環するということは、演算を繰り返して1に収束されるまでに、それらの値が現れないということである。

上位桁に1があるとして、以下のように最下位桁に連続で演算を施すと、取りこぼしなく、すべての桁が有効であるのが分かる(桁を固定するために偶数の演算  N / 2^{n} を省略し、奇数の演算における+1は逆に  + 1 \times 2^{n} を行なう)。

 \hspace{10pt}...0000001 \times 11 + \hspace{20pt}1 =\hspace{5pt}...0000011 +  \hspace{20pt}1 =\hspace{5pt}...0000100
 \hspace{10pt}...0000100 \times 11 + \hspace{10pt}100 =\hspace{5pt}...0001100 +  \hspace{10pt}100 =\hspace{5pt}...0010000
 \hspace{10pt}...0010000 \times 11 + 10000 =\hspace{5pt}...0110000 + 10000 =\hspace{5pt}...1000000


もし有効ではない桁があれば、それによって1に収束しないものもあり得る。それは奇数の演算を変形した  N\times3-1 の場合、最下位桁を削除することにより起こる。

この演算で1に収束する数をみていくと最小値が3、第2位が11であり、その間の5,7,9は1に収束せずに循環してしまうが、これは-1により最下位の値が有効にならないためである。5,7は直接,9は13,19,7へと推移して循環する。

 \hspace{15pt}11(3) \hspace{5pt}\times 11 - 1 = 0001001 - 1 = 0001000(8), \hspace{5pt}0001000(8) \hspace{5pt}/ 10^{11}(2^{3}) \hspace{3pt}= 1
 \hspace{5pt}1011(11) \times 11 - 1 = 0100001 - 1 = 0100000(32), 0100000(32) / 10^{101}(2^{5}) = 1

 \hspace{10pt}101(5) \hspace{5pt}\times 11 - 1 = 0001111 - 1 = 001110(14), 001110(14)   / 10(2)     \hspace{12pt}=  00111(7)
 \hspace{10pt}111(7) \hspace{5pt}\times 11 - 1 = 0010101 - 1 = 010100(20), 010100(20)   / 10^{10}(2^{2})  =  00101(5)
 \hspace{5pt}1001(9) \hspace{5pt}\times 11 - 1 = 0011011 - 1 = 011010(26), 011010(26)   / 10(2)     \hspace{12pt}=  01101(13)
 \hspace{5pt}1101(13) \times 11 - 1 = 0100111 - 1 = 100110(38), 100110(38)   / 10(2)     \hspace{12pt}=  10011(19)
 \hspace{0pt}10011(19) \times 11 - 1 = 0111001 - 1 = 111000(56), 111000(56)   / 10^{11}(2^{3})  = 111000(7)



【値が拡散しない理由】

値の拡散は演算結果が平均して拡大していくことにより起こる。個々の拡大は奇数の演算による。

2進数値において、最上位よりも最下位桁の伸び率の方が十分に高いこと

最終的に1に収束するというのは、奇数の演算だけを行った場合、2進数での最下位桁の1が最上位桁の1に追い付くということである(ここでは青の1が赤の1に)。

通常の演算   奇数だけの演算   最上位と最下位桁の開き
 \require{color}\hspace{10pt}111(7)\hspace{65pt}\textcolor{#ff0000}{1}1\textcolor{#00a0ff}{1}(7)\hspace{35pt} 2
 \require{color}\hspace{5pt}1011(11)\hspace{45pt}\textcolor{#ff0000}{1}01\textcolor{#00a0ff}{10}(22)\hspace{35pt} 3
 \require{color}10001(17)\hspace{35pt}\textcolor{#ff0000}{1}000\textcolor{#00a0ff}{100}(68)\hspace{35pt}4
 \require{color}\hspace{5pt}1101(13)\hspace{30pt}\textcolor{#ff0000}{1}10\textcolor{#00a0ff}{10000}(208)\hspace{30pt}3
 \require{color}\hspace{10pt}101(5)\hspace{25pt}\textcolor{#ff0000}{1}0\textcolor{#00a0ff}{10000000}(640)\hspace{30pt}2
 \require{color}\hspace{20pt}1(1)\hspace{15pt}\textcolor{#00a0ff}{100000000000}(2048)\hspace{25pt}0


2進数での最上位桁は3倍になるのだから安定した状態では  log_2 3 = 1.58 桁の伸びである。最下位桁の伸びである末尾の0は+1により確実に1桁はあり、隣接する上位桁が0であれば桁上げにより2となる。

 \hspace{10pt}01\times11(3)+1 = \hspace{5pt}100  2桁の伸び
 \hspace{10pt}11\times11(3)+1 = 1010  1桁の伸び


隣接する上位桁から先の先まで空いた場合の確率は

 \hspace{10pt}1/2 + 1/2^{2} + 1/2^{3} +...\hspace{5pt}= 1


であり、隣接する上位桁が0の場合と同じく2桁の伸びとなる。したがって最上位桁と最下位桁の伸びの比率は  1.58 / 2 = 0.79 である。これは収束するには十分な比率であり、無限の値でなければ最後は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



値が拡大する状態の判定

 \boldsymbol{(N \times 3 + 1) / 2} の演算結果が奇数になるのは3を法として2と合同な数の最大値であり、この場合のみ偶数演算を施しても拡大する。これは演算前の値の最下位2桁が11の場合に限るが、それは以下の理由による

11より1大きい数100の3倍は3を法として0と合同となる …………(a)
11を3倍して1を加えると3を法として1と合同となる………………(b)
両者を加えると2で割ることができ、かつ2で割ると奇数になる………(c)
以上の演算結果は3を法として2と合同となる……………………………(d)

 \hspace{20pt}100 \times   11      \hspace{15pt}=  1100(12,0) \hspace{1pt}......(a)
 \hspace{25pt}11 \times   11 + 1 =  1010(10,1) ......(b)
 \hspace{15pt}1100 + 1010     \hspace{5pt} = \hspace{5pt}10110       ..........(c)
 \hspace{10pt}10110\hspace{3pt}/\hspace{14pt}  10     \hspace{5pt} = \hspace{5pt}1011(11,2).....(d)


2進数100の3倍が3を法として0と合同となるのだから、下2桁が00の2進数の3倍は必ず3を法として0と合同となる。
したがって、すべての奇数は下2桁が11であれば演算により3を法として2と合同な数の最大値となる。


拡大する状態が有限であること

上位桁に連続する1がある状態で3倍する場合、下2桁は常に01、上2桁が10となり中間は1で詰まる。これは下位からの桁上げがないことと上位の1が途絶えることによる。

 \hspace{25pt}11... \times 11 =   \hspace{15pt}1001...
 \hspace{20pt}111... \times 11 =  \hspace{10pt}10101...
 \hspace{15pt}1111... \times 11 = \hspace{5pt}101101...
 \hspace{10pt}11111... \times 11 = 1011101...


最下位桁に連続する1がある場合は1を加える事により、連続する1は演算前より1桁少ない値となる。つまりこれらの状態で演算を繰り返すと、連続する1の桁数分だけ値が拡大し、その後収束することになる

 \hspace{25pt}11 \times 11 + 1 =   \hspace{15pt}1010
 \hspace{20pt}111 \times 11 + 1 =  \hspace{10pt}10110
 \hspace{15pt}1111 \times 11 + 1 = \hspace{5pt}101110
 \hspace{10pt}11111 \times 11 + 1 = 1011110



したがって、拡大は演算前の値における最下位桁の連続する1によるが、連続する1が有限個であればいずれ収束する

2連続で拡大した後に縮小する例:

 \hspace{15pt}10111(23) \times 11 + 1 =\hspace{5pt}1000110,  \hspace{5pt}1000110 / 10    \hspace{12pt}= 100011(35)
 \hspace{10pt}100011(35) \times 11 + 1 =\hspace{5pt}1101010,  \hspace{5pt}1101010 / 10    \hspace{12pt}= 110101(53)
 \hspace{10pt}110101(53) \times 11 + 1 = 10100000, 10100000 / 10^{101} \hspace{1pt} =   \hspace{15pt}101(5)



発生、消滅を繰り返す場合、拡大の伸び率よりも縮小の伸び率の方が十分に高いこと

拡大できる状態である最下位桁11の値の小さいものを見ると

11(3,0) は3の倍数であるからこれを発生できない。
111(7,1)は1001(9,0)により発生する。

 \hspace{10pt}1001(9)\times11(3)+1=11100(28), 11100\hspace{2pt}/\hspace{2pt}100(4) = 111(7)


9も3の倍数であるからこれを発生できないが、隣接する上位桁に2進数10を追加することによりこれを回避でき、かつ発生させる11の数を同じ桁数だけ増やすことができる。

 \hspace{20pt}  101001(41,2)\hspace{5pt} \times 11(3) + 1 = \hspace{10pt}1111100, \hspace{10pt}1111100 / 100 = \hspace{10pt}11111(31)
 \hspace{10pt}10101001(169,1)            \times 11(3) + 1 = 111111100, 111111100 / 100 = 1111111(127)


発生する値を拡大する条件(最下位桁の連続する1が3桁以上、2桁ずつ)

 \hspace{10pt}...111
 \hspace{10pt}...11111
 \hspace{10pt}...1111111


拡大する値を発生する条件(最下位桁が01で隣接する上位桁に1つ以上の10)

 \hspace{10pt}...1001
 \hspace{10pt}...101001
 \hspace{10pt}...10101001


拡大する値を発生する条件と、桁を減らす01の並んだ条件は3桁以降の0と1の順番が逆の値であり、これらを生成する確率は等しいと言える。しかし拡大/縮小の演算ではその回数が異なり、拡大(拡大桁数)>縮小(1)である。

 縮小
 \hspace{20pt}  010101(21)  \times 11 + 1 =   1000000

 拡大
 \hspace{20pt}  101001(41)\hspace{5pt}  \times 11 + 1 = \hspace{10pt}1111100
 \hspace{25pt}   11111(31)\hspace{5pt}  \times 11 + 1 = \hspace{10pt}1011110
 \hspace{20pt}  101111(47)\hspace{5pt}  \times 11 + 1 = \hspace{5pt}10001110
 \hspace{15pt} 1000111(71)\hspace{5pt}  \times 11 + 1 = \hspace{5pt}11010110
 \hspace{15pt} 1101011(107) \times 11 + 1 = 101000010
 \hspace{10pt}10100001(161)


それぞれの最上位桁と最下位桁との伸び率は、初期値の桁数をTと置くと拡大の演算回数が  T-2 となり

 縮小の演算
 \hspace{50pt}010101
 \hspace{45pt}1000000
  最上位桁(2)/最下位桁(T)
  2/6(T=6)

 拡大の演算
 \hspace{50pt}101001
 \hspace{45pt}1111100
 \hspace{35pt}101111000
 \hspace{25pt}10001110000
 \hspace{20pt}110101100000
 \hspace{10pt}10100001000000
  最上位桁((log_2 3)+(log_2 x(3.5))(T-2))/最下位桁(2+(T-2))
  8.81 / 6(T=6)


拡大した値での最上位桁の伸び率は正確ではないが  log_2 x(x=3.5) としての計算値は  8.81 であるが実際の演算では8未満となる。そこで最上位桁の伸びを8とすると、縮小した値との比は1:4となり、拡大する値の発生、拡大を繰り返しても最終的に収束することになる。さらに演算数の少ない縮小には、演算回数の差である(拡大(T-1)-縮小(1) = (T-2))により  log_2 3 / 2 を比率とした縮小が加わるのである。

  縮小(1/3):拡大(4/3)=1:4


桁数T=114として演算を行なうと、以下の結果が得られる。縮小の方は常に1回の演算を行なうだけなので桁数が増えれば差も広がるのである。

  縮小(2 / 114 = 0.018)\hspace{2pt}/\hspace{2pt}拡大((293-114)/(293-179) = 1.570)\hspace{2pt}=\hspace{2pt}(0.011)

縮小する状態
初期値(桁数114)
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
演算結果-縮小の終了
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
演算回数1回

拡大し続ける状態
初期値(桁数114)
101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001
演算結果-拡大の終了(桁数293、最下位桁179)
10110111000000110100000101010111100111010000101001010001011101110100101110111110111001100111100010000110000011010010010101101100001000010001100011100111000110100110110010110000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
演算回数113回 


なお、 11101(29,2) のような他の状態でも拡大する値は得られるが、1の密度が高くなる( 密度 \gt 1/2)ことにより無駄な値や桁が発生してしまい、拡大効率(拡大回数/初期値の桁数)は悪くなる。

 \hspace{20pt}  11101(29)\hspace{5pt}\times11+1 = \hspace{10pt}1011000
 \hspace{15pt} 111101(61)\hspace{5pt}\times11+1 = \hspace{5pt}10111000
 \hspace{10pt}1111101(125)\times11+1 = 101111000



以上から

演算  (N \times 3 + 1) / 2^{n} を繰り返しても循環することはなく、拡散することもない
∴コラッツの予想は正しい