Project Euler Problem 14

def collatz(cache, n)
  len = 1
  while n != 1
    if n < cache.size and cache[n]
      len += cache[n]
      break
    end
    d, r = n.divmod(2)
    n = r.zero? ? d : 3 * n + 1
    len += 1
  end
  len
end

def f(upper)
  max_n, max_len = 0, 0
  cache = Array.new(upper + 1)
  (1 .. upper).each do |n|
    len = collatz(cache, n)
    cache[n] = len
    if len > max_len
      p [max_n, max_len]
      max_n, max_len = n, len 
    end
  end
  [max_n, max_len]
end

p f(1_000_000)