39 lines
968 B
Ruby
39 lines
968 B
Ruby
module Hailstone
|
|
ListNode = Struct.new(:value, :size, :succ) do
|
|
def each
|
|
node = self
|
|
while node
|
|
yield node.value
|
|
node = node.succ
|
|
end
|
|
end
|
|
end
|
|
|
|
@@sequence = {1 => ListNode[1,1]}
|
|
|
|
module_function
|
|
|
|
def sequence(n)
|
|
unless @@sequence[n]
|
|
m, ary = n, []
|
|
until succ = @@sequence[m]
|
|
ary << m
|
|
m = m.even? ? (m / 2) : (3 * m + 1)
|
|
end
|
|
ary.reverse_each do |m|
|
|
@@sequence[m] = succ = ListNode[m, succ.size + 1, succ]
|
|
end
|
|
end
|
|
@@sequence[n]
|
|
end
|
|
end
|
|
|
|
puts "for n = 27, show sequence length and first and last 4 elements"
|
|
hs27 = Hailstone.sequence(27).entries
|
|
p [hs27.size, hs27[0..3], hs27[-4..-1]]
|
|
|
|
# find the longest sequence among n less than 100,000
|
|
n = (1 ... 100_000).max_by{|n| Hailstone.sequence(n).size}
|
|
puts "#{n} has a hailstone sequence length of #{Hailstone.sequence(n).size}"
|
|
puts "the largest number in that sequence is #{Hailstone.sequence(n).max}"
|