コラッツ予想の謎解き

§０．  
　ある数学者はコラッツ予想について，「数学はまだこの種の問題に対する用意ができていない」と語ったという。果たしてそうなのだろうか？
　ある物理学者は，「簡単なことには簡単な証明がある」と講義のノートに書いた，それから二番目の「簡単」を消して「初等的」と書き直したという。
 （『ファインマンさん，力学を語る』より）
 この言葉を励ましとし，以下，高等数学を用いずに謎解きを試みた。

#### §１．はじめに  
　「コラッツ予想」の自然数についての操作を  
　Ａ：偶数なら，２で割る  
　Ｂ：奇数なら，３倍したのち，１を加える  
と，Ａ,Ｂで表しておくことにする。  
コラッツの予想というのは「どのような自然数も操作Ａ,Ｂの有限回の繰り返しの後，１に終結する」というものである。  
$2$ のベキ $2^n$ 以外は，偶数であっても操作Ａを繰り返せば１以外の奇数になるので，「任意の奇数について成り立つ予想」と言い換えてもよいだろう。  
以下，コラッツ予想を考える出発の自然数は奇数に限定して考える。  

#### §２．奇数生成ツリー  
　コラッツ予想では操作Ａ,Ｂを繰り返すものだが，奇数 $(2n+1)$ に操作Ｂを行うと偶数 $(6n+4)$ になり，次に必ず操作Ａを行うので $(3n+2)$ になる。
ここで，操作Ｂに続けて操作Ａを行うことを新たに操作Ｂ′とし，ＡまたはＢ′ の逆操作として α かつ β を考える。つまり，  
　　『 α：２倍する，　 β：$3n+2$ の形なら，２倍した後１を引いて３で割る 』
  すなわち，
（操作 α）　 ･･･$－\ m\ －\ 2m\ －\ 2^2m\ －\ 2^3m\ －\ 2^4m\ －$･･･
　かつ  
（操作 β）　$･･･－\ (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)$ の形になり得ないので，２倍の枝を伸ばしても奇数を生じさせない。よって，２倍の枝を伸ばす必要はない。
このことは結局，コラッツの操作の途中で３の倍数は現れないことの理由となる。  


#### §３．記号化への準備

自然数を　$\begin{pmatrix} x \\\ y \end{pmatrix} :=3x+y$　という形式でも表すことにする。
よって
　　$1=\begin{pmatrix} 0 \\\ 1 \end{pmatrix}$，$2=\begin{pmatrix} 0 \\\ 2 \end{pmatrix}$，$3=\begin{pmatrix} 1 \\\ 0 \end{pmatrix}$，$4=\begin{pmatrix} 1 \\\ 1 \end{pmatrix}$，$5=\begin{pmatrix} 1 \\\ 2 \end{pmatrix}$，･･･
さらに
　　　　　$ \begin{pmatrix} 0 \\\ 2^2 \end{pmatrix} = \begin{pmatrix} 1 \\\ 1 \end{pmatrix}$
だから，
　　　　　$ \begin{pmatrix} n \\\ 2 \end{pmatrix}$，$ \begin{pmatrix} m \\\ 1 \end{pmatrix}$ 
をそれぞれ $2$ 倍，$2^2$ 倍すると 
　　　　　$ 2\begin{pmatrix} n \\\ 2 \end{pmatrix}=\begin{pmatrix} 2n \\\ 2^{2} \end{pmatrix}=\begin{pmatrix} 2n+1 \\\ 1 \end{pmatrix}$，
　　　　　$ 2^{2}\begin{pmatrix} m \\\ 1 \end{pmatrix}=2\begin{pmatrix} 2m \\\ 2 \end{pmatrix}=\begin{pmatrix} 4m \\\ 2^{2} \end{pmatrix}=\begin{pmatrix} 4m+1 \\\ 1 \end{pmatrix}$
ここで，
　　　　　$f(x)=4x+1,$　$g(x)=2x+1$
とおくと
　　　　　$ 2\begin{pmatrix} n \\\ 2 \end{pmatrix} = \begin{pmatrix} g(n) \\\ 1 \end{pmatrix}$　，　$ 2^{2}\begin{pmatrix} m \\\ 1 \end{pmatrix} = \begin{pmatrix} f(m) \\\ 1 \end{pmatrix}$
右辺は，１を引いて３で割る（操作β）と奇数 $g(n),\ f(m)$ がそれぞれ得られることを示している。

$ \begin{pmatrix} 奇数 \\\ 1 \end{pmatrix}$　を，「奇数を生成する形」と呼ぶことにする。　

#### §４．奇数生成ツリーの記号化と仕組み
　この記法を用いると，奇数生成ツリーの１から伸びる部分（幹）①は
　$1=\begin{pmatrix} 0 \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} 1 \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f^{2}(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f^{3}(1) \\\ 1 \end{pmatrix}$→→･･･　
　　　　　　　　　　　　　｜　　　　　｜　　　　　｜
　　　　　　　　　　　　$f(1)$　　　　$f^{2}(1)$　　　$f^{3}(1)$
　　　　　　　　　　　　$=5$　　　　 $=21$　　　 $=85$
奇数５からさらに伸びる枝②は
　$5=\begin{pmatrix} 1 \\\ 2 \end{pmatrix}$→$\begin{pmatrix} g(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} fg(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f^{2}g(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f^{3}g(1) \\\ 1 \end{pmatrix}$→→･･･
 　　　　　　　　｜　　　　　｜　　　　　｜　　　　　　｜
　　　　　　　$g(1)$　　　　$fg(1)$　　　$f^{2}g(1)$　　　$f^{3}g(1)$
　　　　　　　$=3$　　　　 $=13$　　　 $=53$　　　 $=213$
と表すことができた。ここで，「→」は２倍「→→」は$2^2$倍であり，
また，$fg(1)=f(g(1))$，$f^{2}g(1)=f(f(g(1)))$　などと略した。
整理すると，
『　１を起点とするツリーの幹は
　　$\begin{pmatrix} 0 \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} 1 \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f^{2}(1) \\\ 1 \end{pmatrix}$→→$\begin{pmatrix} f^{3}(1) \\\ 1 \end{pmatrix}$→→･･･
となって，$4=\begin{pmatrix} 1 \\\ 1 \end{pmatrix}$から$\ 2^2$倍ごとに奇数 $f^{n}(1)$$(n\geqq1)$を生成する。
生じた各奇数は２倍してゆくことで，さらに奇数を生成する枝の先頭となる。』
 　 
　枝の初項の奇数を法３で場合分けしてみる。
(ｱ)　初項が $3m$ ( $m$は奇数 ）の枝は，奇数を生成する形は現れない。
　∵　$3m$
　 $=\begin{pmatrix} m \\\ 0 \end{pmatrix}$→$\begin{pmatrix} 2m \\\ 0 \end{pmatrix}$→$\begin{pmatrix} 2^{2}m \\\ 0 \end{pmatrix}$→$\begin{pmatrix} 2^{3}m \\\ 0 \end{pmatrix}$→･･･
(ｲ)　初項が $3m+1$ ( $m$は偶数 ）の枝は，奇数番目毎に奇数を生成する形が現れる。
　∵ $3m+1$ 
　　 $=\begin{pmatrix} m \\\ 1 \end{pmatrix}$→$\begin{pmatrix} 2m \\\ 2 \end{pmatrix}$→$\begin{pmatrix} f(m) \\\ 1 \end{pmatrix}$→$\begin{pmatrix} 2f(m) \\\ 2 \end{pmatrix}$→$\begin{pmatrix} f^{2}(m) \\\ 1 \end{pmatrix}$→･･･
　　　　　　　　　　　　　｜　　　　 　　　　　　｜
　　　　　　　　　　　　$f(m)$　　　　　　　　　$f^{2}(m)$

(ｳ)　初項が $3m+2$ ( $m$は奇数 ）の枝は，偶数番目毎に奇数を生成する形が現れる。
∵ $3m+2$
　 $=\begin{pmatrix} m \\\ 2 \end{pmatrix}$→$\begin{pmatrix} g(m) \\\ 1 \end{pmatrix}$→$\begin{pmatrix} 2g(m) \\\ 2 \end{pmatrix}$→$\begin{pmatrix} fg(m) \\\ 1 \end{pmatrix}$→$\begin{pmatrix} 2fg(m) \\\ 2 \end{pmatrix}$→$\begin{pmatrix} f^{2}g(m) \\\ 1 \end{pmatrix}$･･･
　　　　　　　　｜　　　　　　　　　　｜　　　　　　　　　　　 ｜
　　　　　　　$g(m)$　　　　　　　　$fg(m)$　　　　　　　　　$f^{2}g(m)$


(ｲ)(ｳ)より，１つの枝から生成される奇数は，
　　　　$k$，$f(k)$，$f^{2}(k)$，$f^{3}(k)$，･･･
の形で順に現れるが，　$f(x)\equiv x+1 \ (\ mod \ 3\ )$　だから，この中で奇数のタイプは
　　　･･･，$\equiv0$，$\equiv1$，$\equiv2$，$\equiv0$，･･･　（ $mod \ 3$ ）
のように巡回して現れることもわかる。

#### §５．奇数 n を生成するツリーを作る
　幹や枝は公比２の《無限》等比数列であるが，
[定義]　初項は奇数，公比は２の《有限》等比数列を「小枝」と呼ぶ。
　　　すなわち小枝とは，
　　　　「$a_0$→$a_1$→$a_2$→･･･→$a_k$」（$a_0=$奇数，$a_i=a_0\times2^{i}$）
また，「奇数 $n$ を生成する小枝」とは末項が奇数 $n$ を生成する形になっている小枝を指すものとする。
[定義終]

　奇数生成ツリーの仕組みをふまえると，奇数 $n$ を生成する小枝は，次の (ｴ) または (ｵ) のどちらかの形をしている。
 (ｴ) $ \begin{pmatrix} m \\\ 1 \end{pmatrix}$→･･･→$\begin{pmatrix} f^{k}(m) \\\ 1 \end{pmatrix}$，（$m$は偶数，$n=f^{k}(m),k\geqq1$）
 　　　 　　 　　　　 |
 　　　　　　　　　 $n$             
            
 (ｵ) $ \begin{pmatrix} m \\\ 2 \end{pmatrix}$→$ \begin{pmatrix} g(m) \\\ 1 \end{pmatrix}$→･･･→ $\begin{pmatrix} f^{k}g(m) \\\ 1 \end{pmatrix}$，（$m$は奇数，$n=f^{k}g(m),k\geqq0$）
 　　　　　　　 | 　　　　　　 　 |
 　　　 　 　　 $n$　　または　　 $n$
          
　どんな奇数 $n$ についても，$f^{-1}$ を可能な限り繰り返せば偶数 $m$ または奇数 $g(m)$ になるのは簡単にわかることである。
 しかし，奇数 $n$ を生成する小枝
 　　　　　　　　　$n'$→･･･→$ \begin{pmatrix} n \\\ 1 \end{pmatrix}$
 を作るには (ｴ)・(ｵ) を気にせず，
 　　　『　偶数$ \begin{pmatrix} n \\\ 1 \end{pmatrix}$に単純に操作A を繰り返せばよい　』
ことである。
 そして，この小枝の先頭の奇数 $n'$ を生成する小枝をさらに作り，
 次のように接続すれば「小枝の連鎖（ツリー）」ができる。
 　　　　　　　　 $n''$→･･･→$ \begin{pmatrix} n' \\\ 1 \end{pmatrix}$　B2
 　　　　　　　 　　　　　　 ｜          
 　　　　　　　 　　　　　　 $n'$→･･･→$ \begin{pmatrix} n \\\ 1 \end{pmatrix}$　B1
B1，B2　をさらに　B1，B2，B3，B4，･･･　と伸ばしてゆけばよい。

#### §６．例解
　奇数$25$を例にとる。
 
 $\begin{pmatrix} 25 \\\ 1 \end{pmatrix} =76$ より $19－38－76$　:　$\begin{pmatrix} 19 \\\ 1 \end{pmatrix} =58$ より $29－58$　: 
 $\begin{pmatrix} 29 \\\ 1 \end{pmatrix} =88$ より $11－22－44－88$　:　$\begin{pmatrix} 11 \\\ 1 \end{pmatrix} =34$ より $17－34$　: 
 $\begin{pmatrix} 17 \\\ 1 \end{pmatrix} =52$ より $13－26－52$　:　$\begin{pmatrix} 13 \\\ 1 \end{pmatrix} =40$ より $5－10－20－40$　: 
 $\begin{pmatrix} 5 \\\ 1 \end{pmatrix} =16$ より $1－2－4－8－16$

　小枝を §５の通りに接続すると（枝分かれの " | " は省略）

      1－2－4－8－16
                  5－10－20－40
                             13－26－52 
                                     17－34
                                         11－22－44－88
                                                     29－58
                                                         19－38－76
                                                                 25

#### §７．まとめ
　結局コラッツの操作通りにしてツリーを作るだけで，他には何も新しいことはないように見えているかもしれない。
 しかし，操作Ａ,Ｂの繰り返しというだけでは計算がどこに向かうのか判然としなかったのに対し，本考察では，
　『操作Ａによって作られる小枝を操作Ｂの際に２次元的に接続してできる連鎖を，奇数生成ツリーの上に重ねてみる』
という見方を示してみたつもりである。
そしてコラッツの操作は、
　 『奇数生成ツリーの上を出発点に向かって辿ってゆく「歩き方」を示していた』
と考える。

　ところで §２で奇数生成ツリーを導入した際、紙面に対して
　　　　　操作 α で右に，操作 β で下方に枝を伸ばす
ように，説明なしに図示してきてしまったが，改めて次のようにする。

　『座標平面上の原点に１を置き、
　　　　　操作 α でｘ軸方向に＋１，操作 β でｙ軸方向に－１
　　だけ進んで数を置いてゆく　　　　　　　　　　　　　　』

これにより，
　　　　　奇数生成ツリーの幹上の数はｘ軸上の非負の格子点にあり，
　　　　　ツリーの枝上の数は第４象限内の格子点にある。
また，奇数 $n$ は格子点 $(s,\ t)$ にあるとして，奇数 $n$ を生成する小枝
　　　　　　　　　　$a_0$→$a_1$→$a_2$→･･･→$a_k$
　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　　　　　　$n$
の各数 $a_i$ は格子点　$a_i\ (s-k+i,\ t+1),\ 0\leqq i\leqq k$　に置くものとする。

　例解の奇数 $25$ は，結果的には点$(16,-7)$から「操作Ａによって小枝の長さだけｘ軸に平行に負の方向に進み，操作Ｂで小枝を移る･･･ｙ軸に平行に＋１だけ移動する」ことを繰り返して原点にある１に到達する。
 　コラッツ予想の解説でよく引き合いに出される奇数$27$は，手計算ではなかなか１に終結する様子を見せず（結局操作Ａを70回，操作Ｂを41回），途中で値が $9232$ にもなるが，$27$からの小枝の連鎖は第４象限の中を着実に原点に向かって辿っていたのである。
　他の奇数はどうだろうか。
 
　操作 α かつ β によって導入し，奇数生成ツリーと名付けた構造だが，どんな奇数もこのツリー上のどこかにある，という証明はしていないので「生成」を名前に入れたのは早計に思われるかもしれない。それが証明できればコラッツ予想の証明になるだろう。その直接的な証明は難しいかもしれないが，明らかに
 
　　　どのような奇数に対しても小枝の連鎖を作ることは可能
  
 であり，連鎖の終了がなかなか見えて来ず，また途中で出発の数より大きな数が現れたとしても， 
　　　連鎖は方向性をもって繋がってゆく
のである。
そして操作Ａ,Ｂは連鎖（ツリー）の上を，上方・左方にジグザグと（ループすることなく）辿ってゆく。このツリーは第４象限の中を原点に向かうのであり，その様は減少する自然数の列（有限数列）の如くである。
あるいは，互除法での式の連鎖にも例えよう。ただ，互除法の場合は第１式を立式したときに式の連鎖の有限性は評価できるのに対し，小枝はいくら作り出しても有限性が見えてくるわけではない。小枝の連鎖の有限性は，これが奇数生成ツリーの幹という壁に向かう方向性によって保証される。
すなわち，任意の奇数から有限回の操作Ａ,Ｂの後，１に到達すると考える。
　　　　　　　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/574622/1ddd907c-ba12-3ea7-af56-65a2f74cf894.png)
              
（コラッツ予想の謎解き　終わり）
（参考：Qiita「コラッツ予想と３進法位取り」）