problem137.rb

#Consider the infinite polynomial series A_(F)(x) = xF_(1) + x^(2)F_(2) + x^(3)F_(3) + ..., where F_(k) is the kth term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, ... ; that is, F_(k) = F_(k−1) + F_(k−2), F_(1) = 1 and F_(2) = 1.
#
#For this problem we shall be interested in values of x for which A_(F)(x) is a positive integer.
#Surprisingly A_(F)(1/2)    =    (1/2).1 + (1/2)^(2).1 + (1/2)^(3).2 + (1/2)^(4).3 + (1/2)^(5).5 + ...
#     =    1/2 + 1/4 + 2/8 + 3/16 + 5/32 + ...
#     =    2
#
#The corresponding values of x for the first five natural numbers are shown below.
#x A_(F)(x)
#√2−1  1
#1/2 2
#(√13−2)/3 3
#(√89−5)/8 4
#(√34−3)/5 5
#
#We shall call A_(F)(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 10th golden nugget is 74049690.
#
#Find the 15th golden nugget.

#by using the closed formula for Fibbonaci and the formula for infinite geometric progression, we find that the series sums to x/(1-x-x^2)
#So we can forget about Fibbonaci and concentrate on this function.
#Solving the equation n = x/(1-x-x^2) yields the solutions:
#x_{1,2] = \frac{-\left(n+1\right)\pm\sqrt{(n+1)^2+4n^2}}{2n}
#Therefore, we have a rational x if and only if (n+1)^2+(2n)^2 is itself a square
#i.e. we want a Pythagorean triplet a^2+b^2=c^2
#with a = n+1, b=2n
#i.e. 2a-b=2
#it is well known that every Pythagorean triplet is generated by
#1) a=2kst, b=k(s^2-t^2), c=k(s^2+t^2)
#or
#2) b=2kst, a=k(s^2-t^2), c=k(s^2+t^2)

#In case 1, we have:
#k(4st-s^2+t^2)=2 
#since b is even (b=2n) than we must have k=2
#so we remain with 4st-s^2+t^2=1
#which is Pell's eqution (2s+t)^2-5s^2=1
#i.e. for each x^2-5y^2=1 we gain a solution
#s = y
#t = x-2y
#and so a = 4st = 4y(x-2y)
#and so n = a-1 = 4y(x-2y)-1

#In case 2, we have:
#k(2s^2-2t^2-2st)=2
#and so we must have k=1 and we remain with:
#s^2-st-t^2 = 1
#We substitute t'=(1/2)t and end up with Pell's equation 
#(s-t')^2-5(t')^2=1
#i.e. for each x^2-5y^2=1 we gain a solution
#t' = y
#t = 2t' = 2y
#s = x+y
#and so a = s^2-t^2 = x^2+2xy+y^2-4y^2 = x^2+2xy-3y^2
#and so n = a-1 = x^2+2xy-3y^2-1

#the fundemental solution to x^2-2y^2 = 2 is (3,2)
#the fundemental solution to x^2-5y^2 = 5 is (9,4)
require 'common'

def generate_pell_solutions(n,x,y, max)
    #x,y is the fundemental solution for x^2-ny^2=1
    solutions = [[x,y]]
    current_x, current_y = x,y
    (max-1).times do
        current_x, current_y = x*current_x + n*y*current_y, x*current_y+y*current_x
        solutions << [current_x, current_y]
    end
    return solutions
end

results = []
sol = generate_pell_solutions(5,2,1,20)
sol.each do |pair|
    x, y = pair.first, pair.last
    results << x**2+2*x*y-3*y**2-1 if x**2-5*y**2 == 1
    results << 4*y*(x-2*y)-1 if x**2-5*y**2 == 1
    results << 3*y**2-x**2+2*x*y-1 if x**2-5*y**2 == -1
end

puts results.sort[14]