(5 votes, average: 5.00 out of 5)

Project Euler 137: Determining the value of infinite polynomial series for which the coefficients are Fibonacci numbers.

Problem Description

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.

Analysis

Well, Googling for golden nugget finds a Las Vegas casino or a Denver Basketball team. Fortunately, identifying a pattern emerges quickly after the first few iterations and the solution is simply the product of two consecutive Fibonacci numbers.

Project Euler 137 Solution

Runs < 0.001 seconds in Python 2.7.

Use this link to get the Project Euler 137 Solution Python 2.7 source.

First 10 of the series:

 1 2 2 15 3 104 4 714 5 4895 6 33552 7 229970 8 1576239 9 10803704 10 74049690

Alternate solution without Fibonacci function

```L=2

f1, f2 = 1, 1
for i in range(2*L - 1):
f1, f2 = f2, f1+f2

print "The", L, "golden nugget =", f1*f2
```
Project Euler 137 Solution last updated