問題の定義はコラッツの問題 - Wikipediaを参照。
コードは簡単。数列の形で解を得るようにする。
def collatz(x): lists = [] while x != 1: x = x/2 if x%2 == 0 else x*3 + 1 lists.append(x) return lists
ステップ数を得る場合はlenを使う。
len(collatz(27)) # => 111
2から6000までのコラッツ関数のステップ数を計算してみる。
from matplotlib import pyplot as plt MAXIT = 6000 def collatz(x): lists = [] while x != 1: x = x/2 if x%2 == 0 else x*3 + 1 lists.append(x) return lists cs = [len(collatz(i)) for i in range(2, MAXIT+1)] plt.plot(range(2,MAXIT+1), cs, "ro") plt.show()
傾向を見ると、数の増加とともにステップ数も増加するがパターンがあるし、対数的に増加しているようにも見える。
つづいて、x軸に開始時の数、y軸にcollatz(x)の計算過程における最大の数を取ったグラフを作ってみる(x軸は2から10000まで)。
max_cs = [max(collatz(i)) for i in range(2, MAXIT+1)]
ちなみに開始時の数によってはcollatz計算過程における最大値が非常に大きくなる。2〜10000の間ではcollatz(9663)の計算過程の最大値が最も大きい数27114424になる。よってプロットする際にはylimで描画範囲を絞る必要がある。
plt.ylim(0, 10**6)
ここまで、以下リンクに載っているグラフの真似事でした。
Collatz conjecture - Wikipedia, the free encyclopedia
