Problem 14

正の整数に以下の式で繰り返し生成する数列を定義する。

• n → n/2 (n が偶数)
• n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる。この数列はどのような数字からはじめても最終的には 1 になると考えられているが、まだそのことは証明されていない(コラッツ問題)
さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。

注意: 数列の途中で100万以上になってもよい

Problem 14 - PukiWiki

重いのできっと本当は枝狩りの必要が.

def next_num(num)
  if num % 2 ==0 then
    return (num/2).to_i
  else
    return 3*num+1
  end
end

def calc_path(num,limit)
  return $length[num - 1] if num < limit and $length[num - 1] != nil
  return 1 + calc_path(next_num(num),limit)
end

limit =1000000
$length = Array.new(limit)
$length[0] = 1 

max_num=0
max_val=0

(2..limit).each{|i|
  $length[i-1] = calc_path(i,limit)
  max_num = i and max_val =$length[i-1] if max_val < $length[i-1]
}

p max_num

答え：837799