概要
コラッツ予想が話題になっているため考察してみた。まあ未解決問題なのでそんな簡単に解けるとは思えないが、自分なりのアプローチで考察してみるだけしてみることにした。
プログラム全探索
gist88f0e286049c3efc5cef06158c6ee470
こんな感じのプログラムを書いてみた。つまり1からNまでの全てで成り立っている場合、初期値がN+1ならば一度でも初期値を下回ればOK（それ以降は探索する必要はない）という理屈である。時間計算量と空間計算量がいい感じな探索方法はあまり思い浮かばなかった。
これを一日中走らせた結果、10^9以下では必ず成り立つことはわかった。
まあ、Wikipediaによると既に2^68までは確認されているのでだからどうしたという話にはなる
mod 2^n による考察
まず、初期値が$2k$ならば、$2k\to k\to ?$となる。一方、初期値が$2k+1$ならば$2k+1\to 6k+4\to 3k+2\to ?$となる。
$?$がどうなるかについては、$k$の偶奇に依存する。
初期値のmod 4で区別してみると
$$4k\to 2k\to k\to ?$$
$$4k+1\to 12k+4\to 6k+2\to 3k+1\to ?$$
$$4k+2\to 2k+1\to 6k+4\to 3k+2\to ?$$
$$4k+3\to 12k+10\to 6k+5\to 18k+16\to 9k+8\to ?$$
という感じになる。
初期値のmod 8についても考えてみる
$$8k\to 4k\to 2k\to k\to ?$$
$$8k+1\to 24k+4\to 12k+2\to 6k+1\to 18k+4\to 9k+2\to ?$$
$$8k+2\to 4k+1\to 12k+4\to 6k+2\to 3k+1\to ?$$
$$8k+3\to 24k+10\to 12k+5\to 36k+16\to 18k+8\to 9k+4\to ?$$
$$8k+4\to 4k+2\to 2k+1\to 6k+4\to 3k+2\to ?$$
$$8k+5\to 24k+16\to 12k+8\to 6k+4\to 3k+2\to ?$$
$$8k+6\to 4k+3\to 12k+10\to 6k+5\to 18k+16\to 9k+8\to ?$$
$$8k+7\to 24k+22\to 12k+11\to 36k+34\to 18k+17\to 54k+52\to 27k+26\to ?$$
これを厳密に書き換えてみる。
$n$を正の整数として、$(a_1,b_1)=(2^n,k)$とする。ただし$0\leq k\lt 2^n$とする。
このとき、以下のように有限列を定める。
-
$a_m $が奇数のとき：終了する
- $a_m $が偶数のとき：$b_m $が偶数ならば$(a_{m+1},b_{m+1})=(a_m/2,b_m/2)$、$b_m $が奇数ならば$(a_{m+1},b_{m+1})=(3a_{m},3b_{m}+1)$
このとき、各$k$について初項を$(2^n,k)$と定めたときの最終項$(a_m,b_m)$について、$a_m $の値を$f(n,k)$と定める。
ここで、$f(n,k)\lt 2^n$ならば、初項が$\mod 2^n$で$k$となるような場合にはコラッツの予想は成り立つと考えても良い。いや、具体的に言えば、$\mod 2^n$で$k$になるような数はコラッツ予想の最小の反例にはならないということである。
そして、実験を重ねると$f(n,k)$が常に3の累乗であることが推測できる。
これについても考えてみる。
$n$について、$(2^n,k)$から始めた場合の最終項は$(3^l,b) $となっていると仮定する。
つまり、$2^n m+k $がステップを重ねた結果$3^l m+b$となっているとする。
このとき、$n+1$の場合を考えると
$$2^{n+1} m+(2k)\to 2^n m+k\to \cdots \to 3^l m+b$$
$$2^{n+1} m+(2k)+1\to 3\cdot 2^{n+1} m+6k+4\to 3\cdot 2^n m+ 3k+2$$
ここで、$3\cdot 2^n m + 3k+2 $は$\mod 2^{n+1}$で$2^n m+3k+2$と合同
このとき、$k$が$0\leq k\lt 2^n$を走ったら$3k+2$は$0$以上$2^n$未満の数をすべて網羅することになる。（これは$3$が$2^n$と互いに素であることから従う。）ここで、$a_m $は3倍されることに注意。
よって$f(n,k)=3^l$という形になっていることがわかる。
ここで、$g(n,k)=\log_3 f(n,k)$としておこう。
$0\leq l\leq n$において、$g(n,k)=l$となるような$k$が$p(n,l)$個あるとする。
このとき、$p(n+1,l+1)=p(n,l)+p(n,l+1)$となるから、結局
$p(n,l)={}_nC_{l}$である。以降では$p(n,l)$という表記は使わない。
つまり、$0\leq k\lt 2^n$に対して$g(n,k)$の分布を考えると、これは二項分布となっている。
ここで、$f(n,k)\geq 2^n$というものは、$g(n,k)\geq n \log_3{2}$と言い換えできる。
ここで、$g(n,k)/n \geq \log_3{2}$となるような$k$の存在割合は、中心極限定理により$n\to \infty$で0に収束する。よってコラッツ予想の証明ができ…てない。
たしかに割合としては0に収束しているが、$f(n,k)\geq 2^n$となるような$k$の総数は$n\to \infty$で発散する。
つまり、$2^n$以上$2^{n+1}$未満の数のうち、反例の候補の”割合”は減っていくけど”総数”は増えていく一方なのである。残念
あとこんな議論をして許されるかどうかの確証がない
まあ、お気持ちのガバガバ議論をすると、ほとんどの数で成り立ちそうだな～みたいな気持ちにはなる。あくまでお気持ちだけ。
どうしようもなくなったので、最後に$f(n,k)=3^n$となる場合について考えてみる。
実験してみると$k=2^n-1$のとき$f(n,k)=3^n$となることが推測できる。
よって$2^n-1$を初期値としたときの1に至るまでのステップ数をグラフにしてみた。
すると以下のようになる。
先行研究の存在
Wikipediaに既に載ってた（悲しい）
余談：なぜ3倍して1を足すのか
偶数なら半分はまだいいとして、奇数ならば3倍して1にするのが謎であるというツイートを見かけたので説明してみる。
結論から言うと、他の考えうるパターンだと証明済みか、反例があるかのどちらかである。
パターン1：1倍して1を引く
この場合、任意の初期値に対して0に到達できることが示せる。
初期値が0より真に大きい場合、1ステップ後には必ずもとの数よりも小さくなっているからである。つまり、$a_1\gt a_2\gt a_3\gt \cdots $という自然数の減少列がとれる場合、ある$k$について、$a_{k - 1}\gt a_k=a_{k+1}=a_{k+2}=\cdots $とならなくてはいけない。しかし、このような$ a_k $としてありえるものは$ a_k = 0$しかありえない。つまり必ず0に到達する。
パターン2：1倍して1を足す
この場合も、任意の初期値に対して1に到達できる。
偶数ならば半分するのを繰り返すといずれは奇数となる。このとき、奇数に対して1を足したら必ず偶数となるため、そこから半分にすると必ずもとの奇数以下になる。つまり、操作を繰り返せば必ず減少する。等号が成立するような奇数は1のみであるため、最終的に1に到達できることがわかる。
パターン3,パターン4：2倍して1を引く,2倍して1を足す
この場合は反例がある。奇数に対して2倍して1を足したり引いたりすると結果として奇数が出てきて、さらにもとの奇数よりも大きくなる。つまり無限に増大することを繰り返すため1になることはない。
パターン5,パターン6：2倍して2を引く,2倍して2を足す
2倍して2を引くとき
$k$奇数に対して、$k\to 2k-2\to k - 1$となるためパターン1に帰着される
2倍して2を足すとき
$k$奇数に対して、$k\to 2k+2\to k+1$となるためパターン2に帰着される
いずれの場合も最終的に1または0となることが証明できる。
パターン7：3倍して1を引く
この場合は反例がある。
$$5\to 14\to 7\to 20\to 10\to 5\to 14\to\cdots$$
となってしまうため初期値が5のときはループしてしまう。よってこれが反例になるため成り立たない。
パターン8：3倍して1を足す
コラッツ予想（未解決）
結局、他の候補を考察した結果、3倍して1を足すのが考察のしがいがあるものの中で最もシンプルであることがわかる。
