Detailed mathematical approach

Problem Summary

The Fibonacci generating function is

$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$

A golden nugget is a positive integer value taken by this series for some rational \(x\). Problem 137 asks for the 15th such integer. The key fact used by the implementations is that the nuggets are exactly

$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$

so the requested value is

$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$

Mathematical Approach

The difficult part is not the final multiplication. The real work is to show that the integer values of the generating function occur in a very rigid Fibonacci pattern, so the 15th nugget can be read off from one indexed product instead of found by trial and error.

From the generating function to a quadratic constraint

Assume that the series takes an integer value \(n\), so \(A_F(x)=n\). Then

$\frac{x}{1-x-x^2}=n,$

which rearranges to

$nx^2+(n+1)x-n=0.$

The relevant root is the positive one, namely

$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$

Therefore \(x\) can only be rational if the discriminant

$5n^2+2n+1$

is a perfect square. That turns the original question into a Diophantine condition on \(n\).

A Fibonacci parametrization that produces nuggets

Now introduce the rational numbers

$x_k=\frac{F_{2k}}{F_{2k+1}}.$

The Fibonacci identities immediately explain why these values are special. Starting from Cassini's identity and rewriting it, one gets

$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$

For an even index \(m=2k\), the right-hand side equals \(1\), so

$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$

Divide by \(F_{2k+1}^2\):

$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$

Substituting into the generating function gives

$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$

So every product \(F_{2k}F_{2k+1}\) really is a golden nugget, and it comes from the explicit rational input \(x_k=F_{2k}/F_{2k+1}\).

Why these are all the nuggets

If the discriminant is a square, write

$m^2=5n^2+2n+1.$

Multiplying by 5 and completing the square gives the Pell-type equation

$5m^2-(5n+1)^2=4,$

or equivalently

$(5n+1)^2-5m^2=-4.$

This is exactly the shape of the standard Lucas-Fibonacci identity

$L_t^2-5F_t^2=4(-1)^t.$

For odd \(t\), this becomes \(L_t^2-5F_t^2=-4\), so odd-indexed Lucas and Fibonacci numbers solve the same Diophantine equation. Among those odd indices, the requirement that \(5n+1\) be congruent to \(1\) modulo 5 selects \(t=4k+1\). Hence the admissible solutions satisfy

$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$

Using the standard identity

$L_{4k+1}=5F_{2k}F_{2k+1}+1,$

we obtain

$n=F_{2k}F_{2k+1}.$

So the family produced in the previous subsection is complete: the golden nuggets are precisely the products of consecutive Fibonacci numbers with indices \(2k\) and \(2k+1\).

Worked example

Take \(k=2\). Then

$x=\frac{F_4}{F_5}=\frac{3}{5}.$

From the identity above,

$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$

so

$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$

That is the second golden nugget. The next one comes from \(k=3\): \(x=8/13\) and

$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$

For the required term we take \(k=15\), which yields \(F_{30}F_{31}=1120149658760\).

How the Code Works

The C++, Python, and Java implementations do not search over candidate values of \(x\), and they do not solve the Pell-type equation numerically. They start from the proven closed form

$N_k=F_{2k}F_{2k+1},$

so for the 15th nugget they only need \(F_{30}\) and \(F_{31}\).

Iterating consecutive Fibonacci numbers

The implementation keeps two consecutive Fibonacci numbers and repeatedly advances them to the next pair. The loop invariant is straightforward: after finishing step \(i\), the stored pair is \(F_{i-1}\) and \(F_i\). Starting from \(F_0=0\) and \(F_1=1\), iterating up to \(i=31\) leaves exactly the pair \((F_{30},F_{31})\).

Forming the requested nugget

Once those two values are available, the answer is their product. One implementation also checks the known small case \(N_3=104\) before printing the requested term, which matches the worked example above. Python and Java use arbitrary-precision integers; the C++ version uses a wide fixed integer type, and the 15th nugget still fits comfortably inside it.

Complexity Analysis

For a general index \(k\), the algorithm computes Fibonacci numbers up to \(F_{2k+1}\), so the running time is \(O(k)\). The auxiliary space is \(O(1)\) beyond the storage needed for the integers themselves, because only a constant number of Fibonacci values are kept at any moment.

For this specific problem \(k=15\), the executed workload is tiny: 30 Fibonacci updates and one multiplication. The mathematics is the hard part; the actual computation is effectively constant-time.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=137
2. Fibonacci numbers: Wikipedia - Fibonacci number
3. Generating functions: Wikipedia - Generating function
4. Cassini and Catalan identities: Wikipedia - Cassini and Catalan identities
5. Lucas numbers: Wikipedia - Lucas number
6. Pell's equation: Wikipedia - Pell's equation