夜更かししてしまったので、ツイッターでコラッツ予想について見かけた際に遊んで眺めた様子をメモしておきます。眺めるだけで特に示唆や気付きはありません。
「コラッツ予想」ってヤバい数学の問題があって、何か好きな整数を選んで ・偶数なら半分にする ・奇数なら3倍して1を足す を延々繰り返すと必ず1に行きつくんだけど、めっちゃ簡単そうなのに全人類の誰もこれを証明できてない
コラッツ予想というのは、どんな正の整数も次のルールに従って値を更新していくとやがて1になるというもの。凄くシンプルなのに、まだ証明はされていないらしい。
気になる方はコラッツの問題 - Wikipediaを参照してください。
こういうのはプログラムで書くと色々と遊べて楽しい。
def collatz(x: int) -> int:
if x % 2 == 0:
return x // 2
else:
return 3 * x + 1例えば、コラッツの式で更新をして、何ステップで1に到達するかを数えてみます。
def collatz_count(n: int) -> int:
"""nから始まって何回のステップで1に到達するかを数える"""
count: int = 0
while n != 1:
n = collatz(n)
count += 1
return countこれを1〜500くらいで動かしてプロットしてみると
import matplotlib.pyplot as plt
plt.style.use("ggplot")
n_max: int = 500
collatz_count_list: list = [collatz_count(i) for i in range(1, n_max+1)]
plt.figure(figsize=(16,8))
plt.plot(collatz_count_list)
plt.xlabel("n")
plt.ylabel("collatz_count(n)")
plt.title(f"collatz_count: n=1,...,{n_max}")
plt.show()
流石に折れ線だとグッチャグチャなので scatter でプロットします。
DTMの打ち込み画面みたいなの出てきたな。 リズムに変換したら聴けなくも無かったりするんでしょうか。
1から10000くらいまで動かして、ステップ数が最大のものは何になるか計算してみます。
import numpy as np
n_max: int = 10000
collatz_count_list: list = [collatz_count(i) for i in range(1, n_max+1)]
print(f"max count: {np.max(collatz_count_list)}, n: {np.argmax(collatz_count_list)+1}")実行結果は max count: 261, n: 6171 ということで、1から10000までの整数は全部261ステップ以内で1に到達するということですね。
そこで試しに n=6171 でのステップごとの値の変化をプロットして、1に近づいていく様子を観察してみます。
def collatz_history(n: int) -> list:
result: list = [n]
while result[-1] != 1:
result.append(collatz(result[-1]))
return result
n_start = 6171
plt.figure(figsize=(16,8))
plt.plot(collatz_history(n_start))
plt.xlabel("step")
plt.title(f"collatz_history: start={n_start}")
plt.show()
一旦1e+6くらいまでデカくなってますね。具体的にどんなクソデカ整数が現れるかを見てみます。
def collatz_max_val(n: int) -> int:
"""コラッツ更新中の最大値を返す"""
res = n
while n != 1:
n = collatz(n)
res = max(res, n)
return res
collatz_max_val(6171) # 975400これを使って、コラッツ中（造語）に一番でかい整数を叩き出す初期値を探してみます。
n_max: int = 100
collatz_max_val_list: list = [collatz_max_val(i) for i in range(1, n_max+1)]
plt.figure(figsize=(16,8))
plt.plot(collatz_max_val_list)
plt.xlabel("n")
plt.ylabel("collatz_max_val(n)")
plt.title(f"collatz_max_val: n=1,...,{n_max}")
plt.show()
もっと n_max を大きくしてみましょう。
オーダーを大きくするたびに桁違いにデカいやつがいくつか現れていますね。
他の数字からスタートするとどんな形になるか観察するために、ランダムにでかい整数を引っ張ってきます。
n_starts = [np.random.randint(1e+9) for _ in range(5)]
for n_start in n_starts:
plt.figure(figsize=(16,8))
plt.plot(collatz_history(n_start))
plt.xlabel("step")
plt.title(f"collatz_history: start={n_start}")
plt.show()
全部クソデカ整数ですが、842592789なんかは挙動が大人しく、少ないステップ数で1に到達していますね。
う〜ん、色々やってみたけどやっぱりよく分からん。 受験生のころもコラッツ問題の計算式を紙にいろいろ計算したり、逆に1から辿ってみたりして遊んでいた記憶があるのだけど、なにか発見があるわけでも無かったんですよね。
なんかいい眺め方あったら教えてください。