コラッツ予想

コラッツ予想は、以下の漸化式から、どんな自然数を初項にとっても必ず1に収束する数列ができる、という予想。
ロマンあふれる未解決問題であるが、ミレニアム問題と違って賞金は出ない。

 \displaystyle
    a_{n+1} = 3 a_n + 1

 \displaystyle
    a_{n+1} =  \frac{a_n}{2}

上がaが奇数のときで、下が偶数のとき。
好きな自然数からスタートして、奇数なら3倍して1足す、偶数なら2で割るという操作を繰り返す。
例えば初項17からスタートすると17→52→26→13→40→20→10→5→16→8→4→2→1と無事収束することがわかる。

ぱっと見、「おれでも解けそうじゃね??感」をくすぐる見た目をしているため、俺を含め多くの素人が立ち向かっている。

今回はとりあえず概略的な感じで有名な既出事項をまとめる。

コンピュータの力で「すごく大きな」数までは正しいことが証明されている。

コンピュータで、ひたすら上述の漸化式を計算し、1に収束したらまた次の数を計算、、、という力技。
大きな素数を見つけるプロジェクトと基本的に同じ。
「すごく大きな」数と書いたのは、素数と違って、コラッツ予想は今のところすべて正例のみがヒットしているため、既存の記録がどんどん更新されているはずだから。
100億くらいまで正しかったら、普通にどんな値でも成り立つんじゃないかと思えてしまう。
反例を見つけない限り、数学的な証明にはならないけど、とりあえず前に進もうというスタイル。

確率的に収束するんじゃね?説

奇数を3倍して1足すため、必ず偶数が生成される。偶数は2で割ることになっているので、奇数が出現すると、約1.5倍になる。
一方、偶数が出現したときには、0.5倍。
つまり、奇数が出現した場合の増え具合より、偶数が出現した場合の減り具合のほうが大きいから、奇数と偶数が等しい確率で現れるとするなら、値は小さくなっていくだろう、というもの。
だが、これにも反例があり、問題を奇数のとき3倍して「1引く」に変える(上述の増え具合、減り具合は一緒)と、5→14→7→20→10→5と1を含まないループができてしまう。
まぁ確かに発散はしなさそうだけど、すべての数で1まで下がるとは言えなさそう。

初項より小さい値になればいいんじゃね?説

確かに初項より小さい数へ変形できれば、数学的帰納法よりすべての自然数が1に収束することを言えそう。
偶数は自明なので、だいたいみんな奇数についてのみ考えている。
奇数は2n+1で表せるが、nがさらに偶数2n, 奇数2n+1のときで場合分けして、4n+1と4n+3になる。
このうち4n+1は奇数偶数1回の操作で3n+1になるため、要件を満たす。
一方の4n+3がくせ者で、これを8n+3, 8n+7などの分解していっても、探索範囲が拡大していくだけで解決しそうにない。
ただ、この時点で偶数と4n+1型の奇数あわせて全自然数の75%について、必ず初項より小さくなることが確認できている。

今日はここまでで!