ここでは、以下の二つの補題を証明します。
１．「元のコラッツパターン」の右端が（コラッツ操作が1に収束するまでは）
傾きlog2(3/2)の直線をとる
２．「差のパターン」の右端は、それより大きい傾きで進行する
１．「元のコラッツパターン」の右端が傾きlog2(3/2)の直線をとる
「左端を伸ばすパターン」の右端傾きと「元のコラッツパターン」の右端傾きは一致します。
なぜなら、ルール『最後に、左端に+1する』だけの違いで、
左端からの繰り上がりはどこかで止まるので、
このルールは右端に影響をあたえないからです。
「左端を伸ばすパターン」を数式であらわすと、初期値x、ステップ数nとして
x*(3/2)^nになります。───(ｲ)
オートマトンは2進数で表現しているので、log2の対数目盛に相当します。
なので(ｲ)式の対数を取って
log2x(3/2)n = log2x + log2(3/2)n
= log2x + n*log2(3/2)
傾きをlog2(3/2)とするnの一次式になりました。
以上で１．が証明できました。
２．「差のパターン」の右端は、それより大きい傾きで進行する
初期値17を例にとって、コラッツ操作を連分数で書くと、
17*3+1
─────*3 +1
2*2
───────*3 +1
2*2*2
─────────── = 1
2*2*2*2
きれいにすると
17(3/2)^3 + 3^2/2^3 + 3*[2]/2^2 + [2^3]/2 = 64
一般化します。
x(3/2)^n + 3^(n-1)/2^n + 3^(n-2)/2^(n-1)*□ + ... + 3^1/2^2*□ + 1/2*□ = X
（Xはコラッツ操作が1に収束した時に2^pになります。大きい数です。
証明には使いません。）
□には1か、2のべき乗が入ります。
先頭のx(3/2)^nが「左端を伸ばすパターン」、残りの太字が「差のパターン」に対応しています。
もし、□に全て1が入れば、初項1/2、公比3/2の等比数列になるので、和の公式を使って
以下の不等式が成り立ちます。
(3/2)^n -1 ≦ 3^(n-1)/2^n + 3^(n-2)/2^(n-1)*□ + ... + 3^1/2^2*□ + 1/2*□
「差のパターン」は(3/2)のべき乗より大きいということになります。
以上で２．が証明できました。
証明が不完全なので次回書き直します。
