繰り上がりを考慮した証明
コラッツ予想
nが奇数なら、nを3倍して1を足し2で割る
nが偶数なら、nを2で割る
最終的に１になる
この予想が、初期値ｍに対し、演算結果nが大局的に
n=(3^x)(m/2^y)+1
m/2^yは小数部切り捨て
x,yは自然数
を経由し、(3^x)0+1=1となり予想が正しいということを証明する。
それには、3倍が有限回であることを証明すればよい。
写像１
以下(not)は無限小数2進数表示でビットの反転を表す。
n=(3m+1)/2
-n=(-3m-1)/2
(not)n=-n-1=(3(-m-1)+3-1)/2-1=3(not)m/2
M=(not)m
N=(not)n
と置くと、
Mが偶数の場合、N=3M/2
Mが奇数の場合、N=(M-1)/2
と表せる。
写像２
Mの各ビットを
0は[000]
1は[111]
[000]の3倍は[[000][000][000]]
[111]の3倍は[[111][111][111]]
と表記ことにする。各0や1はコッホ雪片におけるトゲに相当する。3倍を３分割すると読み替えたことでMにおける各ビットの繰り上がりは生じない。
Mの2^z項をMzとすると、M0が0の場合、初期値mが奇数なら、対応するビットm0は１だから、M0の0の個数3^aを使い(3^a-1)/2と置き換えることができる。
後述*1の証明により、有限回aでM0に対する3倍操作が終了する。３と２が互いに疎な素数であることから、Mに対して1/3と1/2によるフーリエ級数による展開を適用することで、1/3と1/2は分離して扱うことができる。
奇数偶数はM０で決まるため、1/2はM０/2と見なせる。
よって、M０以外には[000]か[111]のペアしか存在しない。
結果まとめて
N=(3^a)M/2
Mが奇数の場合、M０の1の個数は3^aなので、初期値mのビットm0は0だから、こちらも一括して、
N=M/2 小数部切捨て
と表せる。ただし、下位からの繰り上がりを考慮すると
N=3(M-1)/2
となる。＊２
ｍは自然数であるから、
Mの0は有限個数であり、1は上位に無限にあるので、Mの下位ビットから順次同様の処理を行うと、
N=・・・111111(2)=・・・111110.111111・・・(2)
に有限回でなる。
よって
n=(not)N=1
に収束することが証明される。
*1）M0が有限回で終了する仮定の証明
上位の桁が3倍されるので+1では差が埋まらないと考えるのは錯覚である。
自身の桁も3倍されているので実際の比率はかわらない。
奇数において
n=3m+1
を繰り返すから
M0=(3^a-1)/2
x=a
とすると
(3^x)(1+3+3^2+3^3+・・・3^(a-1))+(1+3+3^2+3^3+・・・3^(x-1))
=(3^a+1)(3^a-1)/2=((3^a)^2-1)/2
つまりaが求める回数であることがわかる。
＊２繰り上がりを考慮した場合、演算回数は増えるだけで基本ロジックに変更がないことがわかる。
