コラッツ予想とか

3n+1の問題とか、コラッツの問題とか、角谷の問題と呼ばれている、数学の未解決問題。

どんなのかと言うと、

「自然数ｎを選び，
　[1] 奇数ならば，３倍して１をたす。
　[2] 偶数ならば，２で割る。
これを繰り返すと，どんなｎを選んでも，いつかは，１になる」

っていう問題。

フェルマーの定理もそうだけど、問題文がシンプルなほど難しかったりする。

例えば9であれば
9→28→14→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
となって最後は1になる。

30くらいまでは暗算でも簡単に1になることがわかる(27を暗算でやったら凄いです)

解決したとかTwitterに流れてたけど、ソースの論文が英語だったので諦めた。

400兆まで頑張った記録があるらしいけど、そこまでしなくてもって感じがするのでちょっと考えてみる。

とっかかりが難しいので、1から順に考えてみる。
ただし、2のべき乗は明らかに1になるので略。

1⇒自明
2⇒自明
3→10→5→16→略
4⇒自明
5→16→略
6→3→上参照
7→22→11→34→17→52→26→13→40→20→10→5→上参照
8⇒自明
9⇒例参照
10→5→上参照

このようにすれば、偶数であれば、以前に計算したものに辿り着くので、奇数だけ考える。
奇数はまず、3n+1とすると偶数になり、2で割ることになるため、(3n+1)/2と省略できる。

ここで、もし(3n+1)/2が偶数ならば、(3n+1)/4となり(3n+1)/4 < nであるからすでに計算済みである。

奇数ならば、(3n+1)^2/4とよくわからない値になる。これが偶数だとしても元の数より大きいのでまだ続く。

まぁ、それをいつまでも繰り返して、元の数より小さくならなければ、それがコラッツ予想の反例となるわけ。

さて、そんな数があるのかどうか。
困ったときの背理法ということで、「コラッツ予想を満たさない開始数の奇数cがある」とする。
cを問題に従い計算していっても、cを下回ることはない。(理由は上)

しかし、2cは次にcになる。つまりcは開始数ではないので矛盾。

つまり、計算していき無限に増え続ける数はないと。

問題は、ループにはいるパターンである。
1→4→2→1はループになっているが、1があるおかげで、ループを脱出できる。
1がなければ無限ループである！

つまり「開始数cより小さくなることなく、cに戻る数」が反例となる。

ここからはもうわからないからプログラムを書こうと思う。とりあえず方程式っぽいものをメモ程度に残しておくことにしよう。

c = ((3c+1)/2)^n / 2^m
ただし、3^n > 2^(n+m), n > 3(n = 2, m = 0は1を含むループ)

ところでTwitterにあったあの論文は本当なのだろうか…http://twitter.com/alexbellos/status/76055483768766464