Loading...
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.
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
Discussion
No comments yet.