prev |  1 |  2 |  3  |  4 |  5 |  6 |  7 |  next

コラッツ兄弟

  \(3x+1\) の演算をそのままでは理解しにくいので \(2x+x+1\) に分解する。 2進で \(2x\) は \(x\) を1ビット左シフトである。 \(x=01\cdots01_{(2)}\) について見てみる。 図で上段から順に \(2x\) , \(x\) , \(1\) である。
末尾 \(01\cdots01_{(2)}\) はコラッツ変換で末尾が一気に \(0\cdots0_{(2)}\) になる。

図5：末尾 \(01\cdots01_{(2)}\) についての \(3x+1\)

  奇数 \(x\) と \(x'\) の演算結果 \(y\) と \(y'\) について考える。

2進で末尾の \(0\) が1つ多く、すなわち \(y'=2y\) となる場合を求めると \(x'=2x+1/3\) となる。 \(x\) を整数とすると \(x'\) が整数とならないので棄却する。

2進で末尾の \(0\) が2つ多く、すなわち \(y'=4y\) となる場合を求めると \(x'=4x+1\) となる。 これは \(x\) の末尾に \(01_{(2)}\) を追加することに相当する。
\(y\) と \(y'\) の奇数部は同値であるから、\(x\) と \(x'\) のコラッツ変換の結果は同じである。

コラッツ双子

  「上位の値」が同一で「末尾の連続1の数」がひとつ違い（\(2x+1\) の関係）を比べてみる。

        
図6：31と63は結果が一致する（どちらも91）

コラッツ掃出しは並行に進行するが、片方の掃出しが終了したとき、他方は末尾の1がひとつ残っている。 一歩先に終了した側は \(3x+1\) から \(1\) の供給を受け、 遅れた側は掃出しに伴う繰上げから \(1\) の供給を受け、 足並みが揃い、結果が一致する。

遡り展開

  次の図はコラッツ変換の遡り展開である。
青矢印はコラッツ兄弟で矢印方向に \(4x+1\)
緑矢印はコラッツ掃出しで矢印逆方向に \((3x+1)/2\)
赤矢印はコラッツ双子で矢印逆方向に \(2x+1\) である。
紫矢印はコラッツ双子の別表現で矢印逆方向に \(3x+2\) である。

図7：遡り展開 （ダウンロードはこちらSheet2とSheet3で計算方法が異なる）

\(\{1,5,21,85,\cdots\}\) はコラッツ兄弟
\(\{5,3\}\) はコラッツ掃出し
\(\{3,13,53,213,\cdots\}\) はコラッツ兄弟
\(\{53,35,23,15\}\) はコラッツ掃出し
といった具合である。
図では枝の末端から兄弟を伸ばしているが、枝の途中にも兄弟がある。

コラッツ変換 \(x_{i+1}=(3x_i+1)/2\) の逆変換 \(x_{i-1}=(2x_i-1)/3\) は \(x_i\) が \(3\) で割ると \(2\) 余るとき整数になるので、コラッツ兄弟の3個周期でコラッツ掃出しがある。 また、コラッツ掃出しにはコラッツ双子が並行する。 \(\{13,17,11,7\}\) は \(\{53,35,23,15\}\) のコラッツ双子である。

  図を眺めると \(\{1,1\} , \{5,3\}\) がコラッツ双子であること、これが最もプリミティブな構造であり、全体を表していることに気付く。 横には末尾の1が増え、縦には末尾の01が増え、これが横軸縦軸になり、さらに双子は末尾の1がひとつ減り、どんな奇数にも辿り着きそうな気がする。 しかし、コラッツ兄弟/コラッツ掃出し/コラッツ双子を片っ端から開いてみないと、どこにどんな数が隠れているか分からない。 全奇数がこのツリーに繋がっているかどうかは判らない。

prev |  1 |  2 |  3  |  4 |  5 |  6 |  7 |  next