# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2014
#
# コラッツ数列の項を数える
# 重いのでキャッシュ(メモ化)もしとく
def collatz_size(n, mem, k = 0)
  (cache = mem[n]) ? k + cache :
    k +
    if (n == 1)
      1
    elsif (n.even?)
      mem[n] = collatz_size(n / 2, mem, k + 1) - k
    else
      mem[n] = collatz_size(3 * n + 1, mem, k + 1) - k
    end
end
# 100万までの数でコラッツ数列の項の数が最大のものをとる
mem = {}
puts 1.upto(1000000).map {|i| [collatz_size(i, mem), i]}.max.pop