Project Euler 137: Fibonacci golden nuggets

Project Euler 137: Fibonacci golden nuggets

Written by on 23 February 2013

Topics: Project Euler

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.

xAF(x)
√2-11
1/22
(√13-2)/33
(√89-5)/84
(√34-3)/55

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

Which is a traditional quadratic equation which have the solution

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++;
}

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) = 1*2 = 2

F(4)*F(5) = 3*5 = 15

F(6)*F(7) = 8*13 = 104

F(8)*F(9) = 21*34 = 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);
}

with the helper function

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);
}

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.

6 Comments For This Post I'd Love to Hear Yours!

  1. Bjarki Ágúst says:

    I’m pretty sure you have a sign error when you’re solving for . You get , but it should be . Solving for gives us

    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.

  2. Kristian says:

    Thanks for noticing. I have updated the post.

  3. Jean-Marie Hachey says:

    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

  4. Jean-Marie Hachey says:

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

    Apache OpenOffice (AOO)

    http://www.openoffice.org/

  5. Jean-Marie Hachey says:

    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

  6. Michal says:

    I discovered that for even values of Fibonacci, this is correct:

    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]
    

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.