Ruby でコラッツの問題

ja.wikipedia.org
「コラッツの問題」というのは、自然数 n を取り、

  • n が偶数なら2で割る
  • n が奇数なら、3倍して1を足す

という操作を繰り返したところ、どうなるかという問題。じつはこれは難問で、いまだに解決されていない。いまのところ、初期値が268あたりまで、1に帰結することが知られているそうである。

Ruby で計算してみる。初期値が10万までの範囲での、1に至るステップ数の最大値を求めるコードを、再帰で実装する。

def collatz(n, co = 0)
  return co if n == 1
  n.even? ? collatz(n / 2, co + 1) : collatz(3 * n + 1, co + 1)
end

puts (1..10_0000).map(&method(:collatz)).max    #=>350

最大値は350ステップとわかる。実行時間は、僕の環境で0.94秒ほどでした。


350ステップかかるときの初期値を求めてみる。コードの後半をこう書き直す。

max = 0
max_idx = 1
(1..10_0000).each do |i|
  step = collatz(i)
  if step > max
    max = step
    max_idx = i
  end
end
p [max_idx, max]    #=>[77031, 350]

初期値が77031のとき350ステップかかることがわかる。
 

追記

メモ化できるよう、コードを修正してみる。

$memo = {}

def collatz(n)
  return $memo[n] if $memo[n]
  return 0 if n == 1
  sum = n.even? ? collatz(n / 2) : collatz(3 * n + 1)
  $memo[n] = sum + 1
end

puts (1..10_0000).map(&method(:collatz)).max    #=>350

これだと0.12秒で済む。100_0000回までやっても1.5秒ほど、ちなみに初期値が837799のとき、最大値524ステップを取る。もう一桁上げて、1000_0000回までやると、初期値8400511のとき、最大値685ステップ。