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 A_{G}(x) =xG_{1}+x^{2}G_{2}+x^{3}G_{3}+ …, where G_{k}is thekth term of the second order recurrence relation G_{k}= G_{k-1}+ G_{k-2}, G_{1}= 1 and G_{2}= 4; that is, 1, 4, 5, 9, 14, 23, … .

For this problem we shall be concerned with values ofxfor which A_{G}(x) is a positive integer.

The corresponding values ofxfor the first five natural numbers are shown below.

xA_{G}(x)(√5-1)/412/52(√22-2)/63(√137-5)/1441/25

We shall call A_{G}(x) a golden nugget ifxis 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.

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! 🙂

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.

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)

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

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.