Featured image of post コラッツ予想とは？どんな数でも最後は1になる数学の未解決問題をPythonで検証
数学・暗号・量子

コラッツ予想とは？どんな数でも最後は1になる数学の未解決問題をPythonで検証

「偶数は半分に、奇数は3倍して1を足す」を繰り返すと必ず1になる？数学の有名な未解決問題「コラッツ予想」の不思議なルールをわかりやすく解説。さらにPythonでプログラムを書いて、実際に数列が1に収束するかシミュレーションします。

「どんな数字でも最後は1になる」ってほんと？──コラッツ予想を遊んでみた

こんにちは！kenjiです。

突然ですが、「どんな数字でも最終的に1になるルール」って聞いたら、 ちょっと不思議じゃないですか？

例えば、19とか、87とか、1000000でも。 適当なルールに従って数をいじっていくと、なぜか最後は「1」に収束する。

そんな夢みたいな話が、 コラッツ予想（Collatz Conjecture） です。

そもそも、コラッツ予想ってなに？

まずはルールを紹介します。

  • スタート：任意の 正の整数 を選びます

  • 操作：

    • 偶数なら → 半分にする（n → n / 2）
    • 奇数なら → 3倍して1足す（n → 3n + 1）

これをずーっと繰り返していくと、 どんな数字も最終的には1に到達する っていう予想なんですね。

たとえば、6 から始めると：

1

6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

ちゃんと「1」になりました。おかえりなさい！

コードでやってみよう：Pythonでコラッツ

さて、こういうときはコードで試すのが早い！ Pythonで「コラッツ数列」を出力してみましょう。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def collatz(n):
    steps = [n]
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        steps.append(n)
    return steps

# 例：19から始めてみる
print(collatz(19))

実行すると：

1

[19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

みごとに1に到達します。 けっこう寄り道してるのに、最後はしっかりゴールイン！

ちなみに 27 から始めても、同じように1に到達します。

1

print(collatz(27))

実行すると

1
2
3
4
5
6
7
8

[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242,
121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350,
175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167,
502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479,
1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911,
2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732,
866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35,
106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

なんと、111ステップもかかります！

しかも、途中で9000以上まで膨れ上がる場面も。 めちゃくちゃ寄り道してからゴールインするパターンですね。

で、結局なにがすごいの？

この予想の何がすごいかというと、

証明されていないのに、どんな数でやっても1になるっぽい

ってところです。

え？じゃあ、1兆とか、1京（けい）とかは…？

と思った方、鋭い。 実際に計算機を使って「2の68乗」くらいまでは確かめられてて、 すべて1に到達 しています。信じられない…。

でも、 「全部そうなる」と理論的に証明されたわけではない んです。 これが数学の世界でいう「未解決問題」。

なぜ「1」になるの？ 確率論からのアプローチ（数学的背景）

どんな数も最終的に1になるなんて魔法のようですが、 確率的な観点 から見ると「まあ、そうなりそうだよね」という合理的な理由が存在します。

奇数 $n$ に対して 3n + 1 を行うと、答えは必ず 偶数 になります。 したがって、次のステップでは必ず2で割られ、実質的に $\frac{3n + 1}{2} \approx 1.5n$ になります。

そして、その数字がまた偶数になる確率は $\frac{1}{2}$ です。 もし偶数なら、さらに2で割られて $0.75n$ となり、元の数より小さくなります。

数学的に厳密ではありませんが、奇数から次の奇数へジャンプする際の「倍率」の幾何平均をとると、 およそ $\frac{3}{4}$ 倍 になることが知られています（ヒューリスティックな確率モデル）。 つまり、 平均して値は縮小していく傾向にある ため、最終的には1に吸い込まれるように落ちていくのです。

ルールを少し変えるとどうなる？（他の予想との比較）

「じゃあ、3倍じゃなくて5倍にしたら？」と考えたくなりますよね。 実は、 $5n + 1$ 問題 として知られており、この場合はすべての数が1に収束するわけではありません。

$5n + 1$ の場合、複数の異なるループ（循環）が存在することが確認されており、無限に大きくなり続ける数（発散）が存在する可能性も指摘されています。 また、 $3n - 1$ 問題 の場合も、「$1 \to 2 \to 1$」のループのほかに、「$5 \to 14 \to 7 \to 20 \to 10 \to 5$」のような別のループが存在します。

コラッツ予想の「すべてが1（$4 \to 2 \to 1$のループ）に収束する」という性質が、いかに絶妙なバランスの上に成り立っているかがわかります。

人類の到達点①：コンピュータによる総当たりの限界

現在、世界中の数学者やコンピュータサイエンスの愛好家たちが、分散コンピューティング（世界中のPCの計算力を結集するプロジェクト）やGPUを駆使して、ひたすらコラッツ予想を計算し続けています。

2020年の時点で、なんと $2^{68}$（約29京5000兆） 以下のすべての初期値において、コラッツ予想が正しい（最終的に1になる）ことがコンピュータによって確認されています。

しかし、数学の世界では「29京まで確認したから全部正しいだろう」とは言えません。無限に続く数の海からすれば、$2^{68}$ すら「最初の一滴」に過ぎないからです。

人類の到達点②：決定不能性とテレンス・タオのブレイクスルー

「なぜ誰も証明できないのか？」という疑問に対し、イギリスの天才数学者ジョン・コンウェイは1972年に、コラッツ予想を少し拡張した問題が 「決定不能（Turing complete）」である ことを証明しました。 これは、ルールによっては「1に到達するかどうかを判定するアルゴリズムは原理的に存在しない」という、計算機科学の根幹に関わる恐るべき事実です。コラッツ予想そのものも、現代数学の枠組みでは証明不可能な命題である可能性すらあるのです。

ところが2019年、ついに大きなブレイクスルーが起こります。 現代の最高峰の天才数学者の一人である テレンス・タオ（Terence Tao） ** が、「（厳密にすべてとは言えないが） ほとんどすべての初期値において、コラッツ数列は最終的に元の数よりはるかに小さい値に到達する**」ことを偏微分方程式や確率論の手法を駆使して証明したのです。

これは「すべてが1になる」という完全な証明ではありませんが、 人類がコラッツ予想の真理に最も近づいた歴史的な到達点 として、世界中の数学界をどよめかせました。

コラッツさんって誰？

で、ここまで読んで「そもそもコラッツって誰？」って思いますよね。 ちゃんと紹介します！

  • 名前： ローズ・コラッツ（Lothar Collatz）
  • 国籍：ドイツ
  • 生年：1910年〜1990年
  • 肩書き：数学者（関数解析や数論の分野で活躍）

1937年にこの予想を提案して、 その後、80年以上にわたって 誰も証明も反証もできていません 。

ちなみに、この問題はあまりにシンプルなのに奥が深すぎて、 あのポール・エルデシュ（超有名数学者）すらこう言ったとか。

「数学はまだコラッツを扱うには未熟だ」

つまり、人類の数学がこの謎にまだ追いついていない説…。

「難しい数式」は必要ない

コラッツ予想のいいところは、 誰でも遊べる ことです。

紙とペンがあればできます。 Pythonでコードを書けば、自動で試せます。 それでいて、 最先端の数学者たちが本気で挑んでる 。

なんか、ワクワクしません？

おまけ：一気に試すコード

いろんな数字をまとめて試すコードも載せておきますね。

1
2
3

for n in range(1, 21):
    steps = collatz(n)
    print(f"{n}: {steps}（ステップ数: {len(steps)-1}）")

これは「1～20」のコラッツ数列を一気に出してくれます。

結論：この世界、やっぱり不思議だ

というわけで、コラッツ予想。

  • めちゃシンプルなのに
  • 誰も証明できなくて
  • 数学界では大問題

っていう、不思議のかたまりみたいな存在でした。

プログラミング初心者でも試せるので、ぜひ遊んでみてください〜！

おすすめリンク（興味ある人向け）

もっとこういう「不思議系数学×プログラミング」ネタが知りたい人は、 お気軽に「もっと教えて」とリクエストしてみてください。 そのうち、リーマン予想とか素数の話とか、いろいろ紹介しますね！

📮おわり！

comments powered by Disqus