# Project Euler - Problem 14
# http://projecteuler.net/index.php?section=problems&id=14
#
# The following iterative sequence is defined for the set of positive
# integers:
#
# n → n/2 (n is even)
# n → 3n + 1 (n is odd)
#
# Using the rule above and starting with 13, we generate the following
# sequence:
# 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
#
# It can be seen that this sequence (starting at 13 and finishing at 1)
# contains 10 terms. Although it has not been proved yet (Collatz
# Problem), it is thought that all starting numbers finish at 1.
#
# Which starting number, under one million, produces the longest chain?
#
# NOTE: Once the chain starts the terms are allowed to go above one
# million.
 
@cache = { 1 => 1 }
 
def collatz_no_cache(n)
  if n.odd?
    collatz(3 * n + 1)
  else
    collatz(n / 2)
  end
end
 
def collatz(n)
  return @cache[n] if @cache.has_key? n
 
  c = collatz_no_cache(n) + 1
  @cache[n] = c
end
 
max_l, max_n = 0, 0
 
(1...1_000_000).each do |i|
  l = collatz(i)
  if l > max_l
    max_l = l
    max_n = i
  end
end
 
puts "Answer: #{max_n}"