Snippet

project_euler/14.rb

Code:

# Project Euler Problem 14: Longest Collatz Sequence

# https://projecteuler.net/problem=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.
# 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 = {}

def collatz(n)
    return $cache[n] if $cache.key?(n)
    $cache[n] = [n] if n == 1
    $cache[n] = collatz(n % 2 == 0 ? n / 2 : 3 * n + 1) + [n]
end

def solve(bound)
    (2...bound).each { |n| collatz(n) }
    $cache.map { |n, a| [n, a.size] }.sort { |a, b| b[1] <=> a[1] }.first[0]
end

puts solve(1_000)
# puts solve(1_000_000)

Code:

Output: