This problem was a nice departure from the more math and algebra heavy problems I’ve been working on recently. For this one I managed to get the problem working for small numbers then printed out a list of all answers for H(n) for n from 1 to 1000. The more I stared at the numbers, the more patterns I began to see. After studying them for a few days I was able to get a formula for how to derive G(n) when n is a fibonacci number.
def solve(max)
f1, f2 = 3, 2
g1, g2 = 6, 3
loop do
g1, g2 = g1 + g2 + f1, g1
f1, f2 = f1 + f2, f1
return g1 if f1 == max
end
end
puts solve(23416728348467685)
require 'test/unit'
require './problem'
class TestProblem < Test::Unit::TestCase
[
[5, 12],
[8, 23],
[13, 43],
[21, 79],
[34, 143],
[55, 256],
[89, 454],
[144, 799],
].each do |heap, expect|
define_method "test_solve_#{heap.to_s.rjust(3, '0')}" do
assert_equal expect, solve(heap)
end
end
end