コラッツ予想と3進法位取り

#### §１．はじめに  
　「コラッツ予想」の自然数についての操作を  
　Ａ：偶数なら，２で割る  
　Ｂ：奇数なら，３倍したのち，１を加える  
と，Ａ,Ｂで表しておくことにする。  
コラッツの予想というのは「どのような自然数も操作Ａ,Ｂの有限回の繰り返しの後，１に終結する」というものである。  
$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「コラッツ予想の謎解き」）