Project Euler 140: Modified Fibonacci golden nuggets

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.

 x AG(x) (√5-1)/4 1 2/5 2 (√22-2)/6 3 (√137-5)/14 4 1/2 5

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.

$\displaystyle s(x) = \sum_{k=1}^\infty G_k x^k$

$\displaystyle = G_1x + G_2x^2 + \sum_{k=3}^\infty (G_{k-1} + G_{k-2})x^k$

We can insert $G_1 = 1, G_2 = 4$ into the equation and expand the sum

$\displaystyle = x + 4x^2 + x\sum_{k=3}^\infty G_{k-1}x^{k-1} + x^2\sum_{k=3}^\infty G_{k-2}x^{k-2}$

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

$\displaystyle = x + 4x^2 + x\sum_{k=2}^\infty G_{k}x^{k} + x^2\sum_{k=1}^\infty G_{k}x^{k}$

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

$\displaystyle = x + 4x^2 + x(s(x) - x)+ x^2s(x)$

Isolating s(x) gives us

$\displaystyle s(x) = \frac{x + 3x^2}{1-x-x^2}$

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

$\displaystyle k =\frac{x + 3x^2}{1-x-x^2}\Leftrightarrow(3+k)x^2+(1+k)x-k=0$

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

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

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

$b^2 = (1+k)^2 + 4(3+k)k = 5k^2 + 14k +1$

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.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.

Posted by Kristian

Bjarki Ágúst

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

Kristian

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.

Jean-Marie Hachey

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)

Jean-Marie Hachey

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

Kevin McShane

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.

IamLupo

I manage to find a pattern in the golden nuggets. You can generate the nugget one by one without using to generate duplicateds and without having to sort them with a list.

https://pastebin.com/Ne5x7Vm5