§１．はじめに
「コラッツ予想」の自然数についての操作を
Ａ：偶数なら，２で割る
Ｂ：奇数なら，３倍したのち，１を加える
と，Ａ,Ｂで表しておくことにする。
コラッツの予想というのは「どのような自然数も操作Ａ,Ｂの有限回の繰り返しの後，１に終結する」というものである。
$2$ のベキ $2^n$ 以外は，偶数であっても操作Ａを繰り返せば奇数になるので，「任意の奇数について成り立つ予想」と言い換えてもよいだろう。
以下，コラッツ予想を考えるスタートの自然数は奇数に限定して考える。
§２．C形式
コラッツの操作に従って計算してゆくとき（特に手計算では），十進法の表記のまま計算してゆくのは不便である。コラッツの操作を考えると２進法か３進法かの選択になるが，それぞれのトレードオフを考えると，３進法が良いと考える。
$a$ を奇数とし，３進法の位取りでコラッツの操作通りに計算してみよう。
例えば，$a=11$ のとき
操作Ｂ $a ,\ 1\ _{(3)}\ =\ 34\ =\ 2×17$
操作Ａ $2^{-1}${$a,\ 1$}$_{(3)}\ =\ 17$
操作Ｂ $2^{-1}${$a,\ 1$}$,1$$_{(3)}\ =\ 52$
∴ $2^{-1}${$a,\ 1,\ 2$}$_{(3)}\ =\ 2^2×13$
操作Ａ2回 $2^{-3}${$a,\ 1 ,\ 2$}$_{(3)}\ =\ 13$
操作Ｂ $2^{-3}${$a,\ 1,\ 2$}$,\ 1\ _{(3)}\ =\ 40$
∴ $2^{-3}${$a,\ 1,\ 2,\ 2^3$}$_{(3)}\ =\ 2^3×5$
操作Ａ3回 $2^{-6}${$a,\ 1,\ 2,\ 2^3$}$_{(3)}\ =\ 5$
操作Ｂ $2^{-6}${$a,\ 1,\ 2,\ 2^3$}$,1\ _{(3)}\ =\ 16$
∴ $2^{-6}${$a,\ 1,\ 2,\ 2^3,\ 2^6$}$_{(3)}\ =\ 2^4$
操作Ａ4回 $2^{-10}${$a,\ 1,\ 2,\ 2^3,\ 2^6$}$_{(3)}\ =\ 1$
∴ $11,\ 1,\ 2,\ 2^3,\ 2^6\ _{(3)}\ =\ 2^{10}$
これはもちろん，
$11×3^4+1×3^3+2×3^2+2^3×3^1+2^6×3^0\ =\ 2^{10}$
のことである。
同様にして，この形の等式のコレクションを得る。
$3,\ 1 ,\ 2\ _{(3)}\ =\ 2^5$
$5,\ 1\ _{(3)}\ =2^4$
$7,\ 1 ,\ 2 ,\ 2^2 ,\ 2^4 ,\ 2^7\ _{(3)}\ =\ 2^{11}$
$9,\ 1 ,\ 2^2 ,\ 2^3 ,\ 2^4 ,\ 2^6 ,\ 2^9\ _{(3)}\ =\ 2^{13}$
$11,\ 1 ,\ 2 ,\ 2^3 ,\ 2^6\ _{(3)}\ =\ 2^{10}$
$13,\ 1 ,\ 2^3\ _{(3)}\ =\ 2^7$
$15,\ 1 ,\ 2 ,\ 2^2 ,\ 2^3 ,\ 2^8\ _{(3)}\ =\ 2^{12}$
$17,\ 1 ,\ 2^2 ,\ 2^5\ _{(3)}\ =\ 2^9$
$19,\ 1 ,\ 2 ,\ 2^4 ,\ 2^5 ,\ 2^7 ,\ 2^{10}\ _{(3)}\ =\ 2^{14}$
$21,\ 1\ _{(3)}\ =\ 2^6$
$23,\ 1 ,\ 2 ,\ 2^2 ,\ 2^7\ _{(3)}\ =\ 2^{11}$
$25,\ 1 ,\ 2^2 ,\ 2^3 ,\ 2^6 ,\ 2^7 ,\ 2^9 ,\ 2^{12}\ _{(3)}\ =\ 2^{16}$
$27,\ 1 ,\ 2^2 ,\ ･･･,\ 2^{66}\ _{(3)}\ =\ 2^{70}$ （左辺は42桁）
$29,\ 1 ,\ 2^3 ,\ 2^4,\ 2^6,\ 2^9 \ _{(3)}\ =\ 2^{13}$
･･･
この形の等式を $Collatz$ に因んで「$C$形式」と呼ぶことにする。
$C$形式を一般的に述べると次のようになる。
「 $a$ を奇数として
$a,\ 2^{a_1},\ 2^{a_2},\ ･･･,\ 2^{a_m}\ _{(3)}\ =\ 2^{k+a_m}$･･･（＊）
$0=a_1<a_2<a_3<･･･<a_m$ $,\ k$ は $4$ 以上の偶数 」
奇数 $a$ がコラッツ予想に従うならば，適切な
$a_2\ ,\ a_3,\ ･･･,\ a_m,\ k$
によって，式（＊）が成り立つことは計算例から自明だろう。
$m$ は操作Ｂの回数，$k+a_m$ は操作Ａの回数を示す。
$C$形式 $11,\ 1,\ 2,\ 2^3,\ 2^6\ _{(3)}\ =\ 2^{10}$
の最上位「$11,$」を取り除き，等号を「$,$」に置き換え，
$2^0,\ 2^1,\ 2^3,\ 2^6,\ 2^{10}$
に対して，パターンの変換
「$2^m,\ 2^{m+n}\ $」 → 「Ｂ, Ａ($n$)個, 」
をすると
Ｂ, Ａ, Ｂ, Ａ, Ａ, Ｂ, Ａ, Ａ, Ａ, Ｂ, Ａ, Ａ, Ａ, Ａ
この順に操作して奇数$11$ は１に終結する。
§３．奇数生成ツリー
コラッツ予想は操作Ａ,Ｂを繰り返すものだが，奇数 $(2n+1)$ に操作Ｂを行うと偶数 $(6n+4)$ になり次に必ず操作Ａを行うので $(3n+2)$ になる。
ここで，操作Ｂに続けて操作Ａを行うことを新たに操作Ｂ′とし，ＡまたはＢ′ の逆操作として α かつ β を考える。つまり，
α：２倍する
かつ
β：$3n+2$ の形なら，(２倍した後)１を引いて３で割る
すなわち，
（操作 α） $･･･-(m)-(2m)-(2^2m)-(2^3m)-･･･$
であり，
（操作 β） $･･･-(3n+2)-(6n+4)-(12m+8)-･･･$
｜
$(2n+1)$
これにより，１を出発点としてツリー状の構造が出来上がる。
( これを「奇数生成ツリー」と呼ぶことにする )
1－2－4－8－16－32－64－128－256－512ー･･･
｜ ｜ ｜
5･･･ 21 85･･･
（ 操作 β によって４からも１が生じるが，出発の１と同じなので省略する ）
16 から奇数５が生じ，２倍してゆくと更に奇数を生成する枝となる。
5－10－20－40－80－160－320－640･･･
｜ ｜ ｜ ｜
3 13･･･ 53･･･ 213
$3,\ 21,\ 213,\ ･･･$ など３の倍数は２倍を繰り返しても $(3n+2)$ の形になり得ないので，２倍の枝を伸ばしても奇数を生じさせない。よって，２倍の枝を伸ばす必要はない。このことは結局，コラッツの操作の途中で３の倍数は現れないことの理由となる。
§４．奇数生成ツリーとC形式
この奇数生成ツリーにおいて，前節で例として考えた奇数$11$ が現れる部分（$11$ のツリー）は
1－2－4－8－16－･･･
｜
5－10－20－40－･･･
｜
13-26-52－･･･
｜
17-34－･･･
｜
11
ここで，$11$ の$C$形式
$11,\ 1,\ 2,\ 2^3,\ 2^6$ $_{(3)}\ =2^{10}$
の各桁を次のように配置してみると（説明は不要だろう），
$11$
$1,\ 2$
$2,\ 2^2,\ 2^3$
$2^3,\ 2^4,\ 2^5,\ 2^6$
$2^6,\ 2^7,\ 2^8,\ 2^9,\ 2^{10}$
これは，$180^{\circ}$ 回転すると，ツリーと同じ形である。すなわち，ツリーと$C$形式は一対一に対応している，といえよう。
ところで，$C$形式はコラッツの操作から導かれたのであるが，$C$形式が奇数ツリーに対応しているなら，ツリーからも導けるはずである。
実際（$11$の奇数ツリーを見ながら），
$1\ =\ 1$
右に４つ移動（２倍を４回繰り返す）
$16\ =\ 2^4$
下に移動（１を引いて３で割る）
$15\ =\ 2^4-1$
$5\ =\ 0.\ (2^4-1) \ _{(3)}$
右に３つ移動（２倍を３回繰り返す）
$40\ =\ 0.\ (2^7-2^3) \ _{(3)}$
下に移動（１を引いて３で割る）
$39\ =\ (-1).\ (2^7-2^3)\ _{(3)}$
$13\ =\ 0.\ (-1),\ (2^7-2^3)\ _{(3)}$
右に２つ移動（２倍を２回繰り返す）
$52\ =\ 0.\ (-2^2),\ (2^9-2^5)\ _{(3)}$
下に移動（１を引いて３で割る）
$51\ =\ (-1).\ (-2^2),\ (2^9-2^5)\ _{(3)}$
$17\ =\ 0.(-1),\ (-2^2),\ (2^9-2^5)\ _{(3)}$
右に１つ移動（２倍）
$34\ =\ 0.\ (-2),\ (-2^3),\ (2^{10}-2^6)\ _{(3)}$
下に移動（１を引いて３で割る）
$33\ =\ (-1).\ (-2),\ (-2^3),\ (2^{10}-2^6)\ _{(3)}$
$11\ =\ 0.\ (-1),\ (-2),\ (-2^3),\ (2^{10}-2^6)\ _{(3)}$
右辺の負の項を左辺の同じ位に移項して
$11\ .\ 1,\ 2,\ 2^3,\ 2^6\ _{(3)}\ =\ 0\ .\ 0,\ 0,\ 0,\ 2^{10}\ _{(3)}$
小数点を移動すると
$11,\ 1,\ 2,\ 2^3,\ 2^6\ _{(3)}\ =\ 2^{10}$
§５．C形式からC形式を導く
ここまで，コラッツの操作通りにして，あるいは奇数ツリーから$C$形式を導いたが，
すでに$C$形式があれば，これを素にしていくらでも新たに$C$形式を作り出ことができる。
奇数生成ツリーにおいて幹や枝は，初項は奇数，公比は $2$ の等比数列であるが，
(1) 初項が $3m+1$ の奇数なら奇数番目毎に操作βによって奇数を生成する
(2) 初項が $3m+2$ の奇数なら偶数番目毎に操作βによって奇数を生成する
ことに着目する。
例えば
枝：$5$ー$10$ー$20$ー$40$ー$80$ー$160$ー$320$ー$640$ー･･･
$3$ $13$ $53$ $213$
からは，$5$ の$C$形式 $5 ,\ 1\ _{(3)}\ =2^4$ をそれぞれ $2,\ 2^3,\ 2^5,\ 2^7,$ ･･･倍すれば
$\ 2\ ×(\ 5,\ 1\ _{(3)}$ $=2^4\ )$ より $10,\ 2\ _{(3)}\ =2^5$ ∴ $3,\ 1,\ 2\ _{(3)}\ =2^5$
$2^3\ ×(\ 5,\ 1\ _{(3)}$ $=2^4\ )$ より $40,\ 2^3\ _{(3)}\ =2^7$ ∴ $13,\ 1,\ 2^3\ _{(3)}\ =2^7$
$2^5\ ×(\ 5,\ 1\ _{(3)}$ $=2^4\ )$ より $160,\ 2^5\ _{(3)}\ =2^9$ ∴ $53,\ 1,\ 2^5\ _{(3)}\ =2^9$
$2^7\ ×(\ 5,\ 1\ _{(3)}$ $=2^4\ )$ より $640,\ 2^7\ _{(3)}\ =2^{11}$ ∴ $213,\ 1,\ 2^7\ _{(3)}\ =2^{11}$
･･･
また
枝：$13$ー$26$ー$52$ー$104$ー$208$ー$416$ー$832$ー･･･
$17$ $69$ $277$
からは，$13$ の$C$形式 $13 ,\ 1,\ 2^3\ _{(3)}\ =2^7$ をそれぞれ $2^2,\ 2^4,\ 2^6,$ ･･･倍すれば
$2^2\ ×(\ \ 13,\ 1,\ 2^3\ _{(3)}\ =\ 2^7\ \ )$
より $52,\ 2^2,\ 2^5\ _{(3)}\ =2^9$ ∴ $17,\ 1,\ 2^2,\ 2^5\ _{(3)}\ =2^9$
$2^4\ ×(\ \ 13,\ 1,\ 2^3\ _{(3)}\ =\ 2^7\ \ )$
より $208,\ 2^4,\ 2^7\ _{(3)}\ =2^{11}$ ∴ $69,\ 1,\ 2^4,\ 2^7\ _{(3)}\ =2^{11}$
$2^6\ ×(\ \ 13,\ 1,\ 2^3\ _{(3)}\ =\ 2^7\ \ )$
より $832,\ 2^6,\ 2^9\ _{(3)}\ =2^{13}$ ∴ $277,\ 1,\ 2^6,\ 2^9\ _{(3)}\ =2^{13}$
･･･
$3,69,213$ は３の倍数なので，これらの$C$形式からはもう新たな$C$形式は作れないが，その他（３の倍数以外）の$C$形式からは同様にしていくらでも作り出せる。
尚，上記の例において，
$f(x)=4x+1,\ g(x)=2x+1$
とおくと，
$5\ (3m+2タイプ)\ $の枝から生成される奇数は，$(5-2)/3=1$ より
$g(1)=3,\ fg(1)=13,\ f^2g(1)=53,\ f^3g(1)=213,\ $･･･
$13\ (3m+1タイプ)\ $の枝から生成される奇数は，$(13-1)/3=4$ より
$f(4)=17,\ f^2(4)=69,\ f^3(4)=277,\ $･･･
であることを注意しておきたい（「コラッツ予想の謎解き」参照のこと）。
（コラッツ予想と３進法位取り 終わり）
（参考：Qiita「コラッツ予想の謎解き」）