【Project Euler】Problem 14: 最長のコラッツ数列

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 14. 最長のコラッツ数列

原文 Problem 14: Longest Collatz sequence

問題の要約： $N<10^6$ で最長のコラッツ数列となる開始の数を求めよ

昨年朝日新聞にも「「コラッツ予想」証明できたら１億２０００万円」で紹介されたコラッツ数列の問題ですね。定義はコラッツの問題(Wikipedia)に詳細があります。問題そのものは定義に沿って書けば簡単で、数列の長さを求める関数collatzLenは以下のようになります。

import itertools
def collatzLen(n):
  for cnt in itertools.count(2):
    n = n // 2 if n % 2 == 0 else 3*n + 1
    if n == 1: break
  return cnt

termmax = 0
N = 10**6
for n in range(2, N):
  term = collatzLen(n)
  if term > termmax: 
    startn, termmax = n, term
print(f"Answer : {termmax} at n={startn}")

これだけだと面白くないのでWikipediaにもあるグラフをmatplotlibで書いてみました。x軸がnで、y軸が数列の長さです。1つだけ飛び出ているのが答えですね。プログラムは下にあります。

import matplotlib.pyplot as plt
N = 10**6
fig = plt.figure(figsize=(12,12))
ax = fig.add_subplot(1, 1, 1)
ax.set_xlim(0, N) 
ax.set_ylim(0, 600) 
ax.grid()

for n in range(1,N+1,2):
  cs = collatzLen(n)
  ax.plot(n, cs, marker='.',markersize= 3, color='b')
plt.show

（開発環境：Google Colab）