 # Project Euler 137: Fibonacci golden nuggets

I think that Problem 137 of Project Euler is a really fantastic problem since it has so many facets of how it can be solved. I will go through a one of them, and then link to a few other. The problem reads

Consider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + …, where Fk is the kth term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, … ; that is, Fk = Fk-1 + Fk-2, F1 = 1 and F2 = 1.

For this problem we shall be interested in values of x for which AF(x) is a positive integer.

 Surprisingly AF(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 AF(x) √2-1 1 1/2 2 (√13-2)/3 3 (√89-5)/8 4 (√34-3)/5 5

We shall call AF(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.

I honestly don’t know a whole lot about infinite series, and I am always quite intimidated by them. However, I know enough about them to know that there is something called a generating function which should be the keyword here. Searching for Fibonacci generating function lands us on Wikipedia as the first hit.

This gives us a generating function as

So we to turn that around a bit, since we want to see if x is a rational number for an integer value of . So for a given integer value n, we can rewrite the equation to

This will give us a rational solution if the square root part is an rational. Something which only happens if it is integer. So we can find solutions where  is integer.

I started doing that knowing very well that it would likely take a very long time if I didn’t get into overflow problems before that. But I wrote the code

long k = 1;
int count = 0;
int limit = 15;

while (count < limit) { long discriminantSquared = (k+1)*(k+1) + 4*k*k; long discriminant = (long) Math.Sqrt(discriminantSquared); if(discriminant*discriminant == discriminantSquared){ Console.Write((count + 1) + ": " + discriminant + " "); Console.Write((k + 1) * (k + 1) + 4 * k * k + " "); Console.WriteLine(k); count++; } k++; } [/csharp] This works up to around the 11th nugget, after which I ran into overflow problems. However, it gave us a clue as what to do. Namely the integer sequence 2, 15, 104, 714, 4895, 33552... Looking a bit at that it struck me that 104 = 8* 13, which just happens to both be Fibonacci numbers.  Digging a bit more into that I realized that F(2)F(3) = 12 = 2

F(4)F(5) = 35 = 15

F(6)F(7) = 813 = 104

F(8)F(9) = 2134 = 714

Or in general F(2n)*F(2n+1) is the solution to finding the nth golden nugget. I know this requires some leap of imagination to figure this out, and I guess I realized it by chance. However, looking the sequence up on OEIS confirms both the sequence as well as the formula in sequence A081018. So all of a sudden we can reduce the problem to calculate to Fibonacci numbers. Something which have a solution as

So all of a sudden we can solve the problem in O(1) complexity.

I wrote a small loop to get all the nuggets up to the limit. Which looks like

long result = 0;

for (int k = 1; k < 16; k++) { result = Fibonacci(2*k)*Fibonacci(2*k+1); Console.WriteLine(result); } [/csharp] with the helper function [csharp] public long Fibonacci(long k) { double sqrt5 = Math.Sqrt(5); return (long) (( Math.Pow((1 + sqrt5) / 2, k) - Math.Pow((1 - sqrt5) / 2, k))/sqrt5); } [/csharp] Which gives us the result in 2.5ms.

## Wrapping up

First of all you can find the source code I wrote here.

But this was my solution for this time. However, there are several good writeups out there. Bobby Lobster wrote a two part blog post about it where he uses Conway’s topograph to solve it.  Robert Haramoto solved it by rewriting the generating function as a Pell’s equation and then solving that. ### Posted by Kristian Bjarki Ágúst

I’m pretty sure you have a sign error when you’re solving for $x$. You get $n(-x^2-x-1) = x$, but it should be $n(-x^2-x+1) = x$. Solving for $x$ gives us

$\displaystyle x = \frac{n+1 \pm \sqrt{(n+1)^2 + 4n^2}}{-2n}$

But great post. I bruteforced the first couple of values and then did an OEIS search, which led me to the same formula. But now I’ve got more insight into the next problem, which is very similar, but I have yet to solve. Kristian

Thanks for noticing. I have updated the post. Jean-Marie Hachey

I simply used Microsoft Office Excel (2007)
to generate the following list.
(Limitations: my version of Excel is limited to 15 digits).
So the list was stopped at the 18th Fibonacci
golden nugget.

___

Table 1
List of Fibonacci golden nuggets
[Re: Project Euler 137: Fibonacci golden nuggets]

http://img23.imageshack.us/img23/8241/pe137fibonaccitabone.jpg Jean-Marie Hachey

The same limit (15 digits) is observed for the spreadsheet from OpenOffice (version 3.4.1)

Apache OpenOffice (AOO)

http://www.openoffice.org/ Jean-Marie Hachey

Table 2

Seven as a factor in the generation of Fibonacci golden nuggets.
[Re: Project Euler 137: Fibonacci golden nuggets]

http://img138.imageshack.us/img138/9783/pe137fibonaccitabtwo.jpg Michal

I discovered that for even values of Fibonacci, this is correct:
$F_i = 18F_{i-2} – F_{i-4}$

but we need to calculate first four terms.

Why I got these 18 ?

#!/usr/bin/env python
fib = [0,2,8,34]
n=len(fib)
for i in xrange(n,n+1000):
F = 18*fib[i-2] - fib[i-n]
if F>=4000000: break
fib.append(F)
print sum(fib),fib

# OUTPUT:
#./fibo.py
#4613732 [0, 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040,  3524578] Dr. Stefan Gruenwald

Here is my python 2.7 version, which runs in 0.073 milliseconds:

def fib(n,a=1,b=1):
while n&gt;1:
n-=1
a,b=a+b,a
return b

def golden_nugget(m):
return fib(2*m)*fib(2*m+1)

print golden_nugget(15)