Project Euler 140: Modified Fibonacci golden nuggets

Project Euler 140: Modified Fibonacci golden nuggets

Written by on 16 March 2013

Topics: Project Euler

Problem 140 of Project Euler is very much a continuation of the Problem 137, as we can see from the problem description

Consider the infinite polynomial series AG(x) = xG1 + x2G2 + x3G3 + …, where Gk is the kth term of the second order recurrence relation Gk = Gk-1 + Gk-2, G1 = 1 and G2 = 4; that is, 1, 4, 5, 9, 14, 23, … .

For this problem we shall be concerned with values of x for which AG(x) is a positive integer.

The corresponding values of x for the first five natural numbers are shown below.

xAG(x)
(5-1)/41
2/52
(22-2)/63
(137-5)/144
1/25

We shall call AG(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 20th golden nugget is 211345365.

Find the sum of the first thirty golden nuggets.

In Problem 137 I mentioned in the end that the problem could be solved using a Diophantine equation. This is exactly the way I will go for this problem.

Finding the generating function

However, in order to do that we need to derived the generating function for this problem. On Wikipedia the generating function for the Fibonacci numbers were derived. So we will just follow the same recipe.

We can insert into the equation and expand the sum

Furthermore I have pulled a number of x out from the sum to give the G and x inside the sum the same index. The sums that can be rewritten as

The last sum is s(x), and the first sum corresponds to . We can insert and get

Isolating s(x) gives us

If we plug the given x from the table in the problem description we will get the correct results, indicating that we are right.

Finding the solution

We know that s(x) should be an integer, so let us denote it k and plug that into the generating function, we then get that

Which is a quadratic function with the solution (I think we learned this in primary school)

This will only have a rational solution when the square root part is rational. Which in turn will only happen if the square root part is integer. So let b be an integer such that

This has the form of a quadratic Diophantine equation, which we can solve with the magic tool of  Dario Alpern’s Generic Two integer variable  equation solver.

The result from there gives us a whole lot of different start values. So I have implemented my method to try them all and then just add solutions that are positive. This is implemented in C# as

 long result = 0;
 long[,] start = new long[,] { {  0, -1 },
                               {  0,  1 },
                               { -3, -2 },
                               { -3,  2 },
                               { -4, -5 },
                               { -4,  5 },
                               {  2, -7 },
                               {  2,  7 } };
List<long> nuggets = new List<long>();

for (int j = 0; j < start.GetLength(0); j++) {
    long k = start[j, 0];
    long b = start[j, 1];

    for (int i = 0; i < 30; i++) {
        long knew = -9 * k + -4 * b + -14;
        long bnew = -20 * k + -9 * b + -28;

        k = knew;
        b = bnew;

        if (k > 0 && !nuggets.Contains(k))
            nuggets.Add(k);
    }
}

nuggets.Sort();
for (int i = 0; i < 30; i++)
    result += nuggets[i];

This gives us the solution in 0,09ms. So that is really nice. And quite a bit shorter time than I used to derive the solution.

Wrapping up

You can rewrite the quadratic Diophantine equation to a Pell’s equation by substituting a bit. I know that has been done several places. But I didn’t want to take that additional extra step since we can solve the first equation just fine.

As always you can find the source code here.

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

  1. Bjarki Ágúst says:

    We just started learning about generating functions in the Abstract Algebra and Combinatorics course yesterday. I, of course, immediately took another look at this problem. I did the exact same thing as you did, used Dario’s diophantine equation solver after I had found the closed form of the ordinary generating function. It’s nice to see that school is already paying off! 🙂

  2. Kristian says:

    That sounds good. You will need to write something about it at some point then. Since I am still not sure I actually understand the finer points about them.

  3. Jean-Marie Hachey says:

    Table 1
    Modified Fibonacci golden nuggets (cumulative and specific).
    [Re: Project Euler 140: Modified Fibonacci golden nuggets]

    http://img43.imageshack.us/img43/2847/pe140tabl1mfibonacci.jpg

    The 20th modified golden nugget in the table (247 447 450) is different from the one reported in the article (211 345 365). We can observe that this difference is equal to the value of the 18th specific golden nugget appearing in Table 1 (36 102 085).

    ___

    Sources:

    1) Project Euler 140
    Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem140.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  4. Jean-Marie Hachey says:

    Concerning the sum of the first 30 modified Fibonacci golden nuggets, the output of the algo and the result of Table 1 are the same …

    http://img543.imageshack.us/img543/3900/pe140algotabl1.jpg

  5. Kevin McShane says:

    If g(i) is the i-th golden nugget, for even values of i we have

    g(i) = G(i)*F(i),

    where F is the standard Fibonacci sequence.

    You can also remove the Diophantine solutions (2,7) and (2,-7). They generate the same values as two of the other solutions.

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=""> <s> <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

This site uses cookies.