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

#### Problem Description

Consider the infinite polynomial series A_{F}(*x*) = *x*F_{1} + *x*^{2}F_{2} + *x*^{3}F_{3} + …, where F_{k} is the *k*th term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, … ; that is, F_{k} = F_{k−1} + F_{k−2}, F_{1} = 1 and F_{2} = 1.

For this problem we shall be interested in values of *x* for which A_{F}(*x*) is a positive integer.

Surprisingly A_{F}(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 |
A_{F}(x) |

√2−1 | 1 |

1/2 | 2 |

(√13−2)/3 | 3 |

(√89−5)/8 | 4 |

(√34−3)/5 | 5 |

We shall call A_{F}(*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.

#### Comments

- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A081018: (Lucas(4n+1)-1)/5, or Fibonacci(2n)*Fibonacci(2n+1)

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*

## Discussion

## No comments yet.