project-euler/Sidef/137 Fibonacci golden nuggets.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Website: https://github.com/trizen

# https://projecteuler.net/problem=137

# Runtime: 0.154s

# I first derived a closed-form to the infinite sum:
#
#                             -(x / (x^2 + x - 1))
#
# then a reverse to that:
#
#                             R(x)= (sqrt(5x^2 + 2x +1) - x - 1) / (2x)
#
# after which I discovered that:
#
#                             R(Fn ∗ F(n+1))= Fn / F(n+1)
#
# simplifying the problem to just:
#
#                             Fn ∗ F(n+1)

var max = 15

func fib(n) is cached {
    n > 1 ? (fib(n-1) + fib(n-2)) : n
}

say (fib(2*max) * fib(2*max + 1))