Skip to content

Instantly share code, notes, and snippets.

@thiagoa
Created Jul 13, 2017
Embed
What would you like to do?
class Collatz
def initialize(min, max)
@min = min
@max = max
@cache = Array.new(max, 0)
end
def longest_length
max_n, max_length = 0, 0
(@min..@max).each do |n|
length = length_for(n)
if length > max_length
max_n, max_length = n, length
end
end
[max_n, max_length]
end
private def length_for(n)
@cache[n - 1] = next_for(n)
end
private def next_for(n)
return 1 if n == 1
return @cache[n - 1] if n <= @max && @cache[n - 1] != 0
if n.even?
1 + next_for(n / 2)
else
1 + next_for(n * 3 + 1)
end
end
end
collatz = Collatz.new(1, 1_000_000)
max_n, max_length = collatz.longest_length
puts "Number with longest Collatz sequence: #{max_n}"
puts "Longest sequence length: #{max_length}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment