Problem 137: Fibonacci Golden Nuggets

Project Euler Problem 137 Solution

EulerSolve provides an optimized solution for Project Euler Problem 137, Fibonacci Golden Nuggets, with C++, Python, Java, and a step-by-step mathematical explanation.

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

Detailed mathematical approach

Problem Summary

The Fibonacci numbers are defined by $F_1=F_2=1$ and $F_k=F_{k-1}+F_{k-2}$, so they begin $1,1,2,3,5,8,\dots$. The problem studies the infinite series

$$A_F(x)=xF_1+x^2F_2+x^3F_3+\cdots$$

and the values of $x$ for which it is a positive integer. Such an integer is called a golden nugget when its $x$ is rational. The statement shows that at $x=\tfrac12$ the series is

$$\tfrac12+\tfrac14+\tfrac28+\tfrac3{16}+\tfrac5{32}+\cdots=2,$$

lists the values $\sqrt2-1$, $\tfrac12$, $\tfrac{\sqrt{13}-2}3$, $\tfrac{\sqrt{89}-5}8$ and $\tfrac{\sqrt{34}-3}5$ of $x$ at which the series equals $1$, $2$, $3$, $4$ and $5$, and says that the $10$th golden nugget, counting in increasing order, is $74049690$. We must find the $15$th golden nugget. ^[1]

The whole solution in one sentence: the golden nuggets are exactly the products $1\cdot2$, $3\cdot5$, $8\cdot13$, … of every second pair of neighbouring Fibonacci numbers, the $k$-th one being $F_{2k}F_{2k+1}$, because the series equals $x/(1-x-x^2)$, and for a positive fraction $x=p/q$ in lowest terms this is a positive integer exactly when $q^2-pq-p^2=1$, an equation whose positive solutions are exactly these pairs.

Mathematical Approach

We turn the series into a fraction, find out where it converges, look at the first nuggets, and then prove the pattern they show by running the Fibonacci rule backwards.

1. The series as a fraction

Suppose that the series converges, and write $A$ for its value. In $A-xA-x^2A$ the coefficient of $x$ is $F_1=1$, the coefficient of $x^2$ is $F_2-F_1=0$, and for $k\ge3$ the coefficient of $x^k$ is $F_k-F_{k-1}-F_{k-2}=0$. Only $x$ is left, so $(1-x-x^2)A=x$ and

$$A_F(x)=\frac{x}{1-x-x^2}.$$

A power series whose coefficients form a given sequence is its generating function, so this fraction is the generating function of the Fibonacci numbers in closed form. ^[2] At $x=\tfrac12$ the denominator is $1-\tfrac12-\tfrac14=\tfrac14$, so $A_F(\tfrac12)=2$, as the statement says. The series itself approaches $2$ slowly: after $10$, $20$ and $40$ terms the remaining gap is about $0.228$, $0.0273$ and $0.00039$, and from one term to the next the gap is multiplied by a ratio that tends to $\varphi/2\approx0.809$, with the golden ratio $\varphi$ of Section 2.

2. Where the series converges

Let $\varphi=(1+\sqrt5)/2\approx1.618$ be the golden ratio, the positive root of $\varphi^2=\varphi+1$. ^[2] The Fibonacci numbers grow like its powers:

$$\varphi^{k-2}\le F_k\le\varphi^{k-1}\qquad(k\ge1).$$

Both bounds hold for $k=1$ and $k=2$, and if they hold for $k-2$ and $k-1$, adding them gives the bounds for $k$, because $\varphi^{j}+\varphi^{j+1}=\varphi^{j+2}$. For $|x|\lt1/\varphi\approx0.618$ the $k$-th term therefore has absolute value at most $|x|\,(\varphi|x|)^{k-1}$, so the series converges absolutely by comparison with a geometric series of ratio $\varphi|x|\lt1$, which also justifies the rearrangement in Section 1. For $|x|\ge1/\varphi$ the terms have absolute value at least $\varphi^{-2}$ and do not tend to $0$, so the series diverges.

On the interval $-1/\varphi\lt x\lt1/\varphi$ the denominator $1-x-x^2=(1/\varphi-x)(\varphi+x)$ is positive. Negative $x$ therefore give negative values, and on $0\lt x\lt1/\varphi$ the value $A_F(x)$ grows continuously from $0$ to $+\infty$, because all coefficients are positive and the denominator tends to $0$ at the right end. Hence every positive integer $n$ is the value of the series at exactly one point $x_n$, with $0\lt x_n\lt1/\varphi$, and $n$ is a golden nugget exactly when $x_n$ is rational.

3. Solving $A_F(x)=n$

Setting the fraction equal to $n$ and clearing the denominator gives the quadratic equation

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

Its two roots have the product $-1$, so one is positive and one is negative, and the positive one is

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

The other root, $-1/x_n$, is smaller than $-\varphi$, where the series diverges, although the fraction equals $n$ there too: for $n=2$ it is $x=-2$, and $-2/(1+2-4)=2$. Only the positive root is a value of the series. A square root of a positive integer is rational only when the integer is a perfect square, ^[3] so $n$ is a golden nugget exactly when $5n^2+2n+1$ is a perfect square. For $n=1,2,3,4,5$ this number is $8$, $25$, $52$, $89$ and $136$. Only $25=5^2$ is a square, which gives $x_2=(-3+5)/4=\tfrac12$; the others give the irrational values of the statement, for example $\sqrt{52}=2\sqrt{13}$ and $x_3=(\sqrt{13}-2)/3$.

4. The first nuggets by search

Testing $5n^2+2n+1$ for every $n\le10^6$ finds exactly seven golden nuggets: $2$, $15$, $104$, $714$, $4895$, $33552$ and $229970$. By the formula of Section 3 their values of $x$ are $\tfrac12$, $\tfrac35$, $\tfrac8{13}$, $\tfrac{21}{34}$, $\tfrac{55}{89}$, $\tfrac{144}{233}$ and $\tfrac{377}{610}$. Each $x$ is a ratio of consecutive Fibonacci numbers with an even index on top, $F_{2k}/F_{2k+1}$, and each nugget is the product of its numerator and denominator: $15=3\cdot5$, $104=8\cdot13$, $714=21\cdot34$. The next sections prove that this always happens.

5. Fractions in lowest terms

Write a positive rational $x$ as $p/q$ with positive integers $p$ and $q$ whose only common positive divisor is $1$. Multiplying the numerator and the denominator of the fraction of Section 1 by $q^2$ gives

$$A_F\Bigl(\frac pq\Bigr)=\frac{pq}{q^2-pq-p^2}.$$

For $x=\tfrac35$ the denominator is $25-15-9=1$ and the value is $15$; for $x=\tfrac13$ it is $9-3-1=5$, and the value $\tfrac35$ is not an integer.

Claim. If $0\lt p/q\lt1/\varphi$, with $p$ and $q$ coprime, and $A_F(p/q)$ is an integer, then $q^2-pq-p^2=1$ and the value is $pq$.

Proof. Put $d=q^2-pq-p^2$. By Section 2, $d/q^2=1-x-x^2\gt0$, so $d$ is a positive integer that divides $pq$. Suppose that a prime $r$ divides both $d$ and $pq$. By Euclid's lemma, ^[4] $r$ divides $p$ or $q$. If $r$ divides $p$, it divides $d+pq+p^2=q^2$ and hence $q$; if $r$ divides $q$, it divides $q^2-pq-d=p^2$ and hence $p$. Either way the prime $r$ divides both $p$ and $q$, which is impossible. So $d$ and $pq$ have no common prime factor, and the only divisor of $pq$ with this property is $d=1$.

Conversely, if positive integers satisfy $q^2-pq-p^2=1$, they are coprime, because every common divisor of $p$ and $q$ divides $1$, and $x=p/q$ satisfies $1-x-x^2=1/q^2\gt0$, so it lies in the interval of convergence and $A_F(x)=pq$. The golden nuggets are therefore exactly the products $pq$ of the positive solutions of $q^2-pq-p^2=1$.

6. Running the Fibonacci rule backwards

Put $D(a,b)=b^2-ab-a^2$. The Fibonacci rule moves a pair of neighbours one place along the sequence, $(F_j,F_{j+1})\mapsto(F_{j+1},F_{j+2})$, that is, $(a,b)\mapsto(b,a+b)$. The reverse step is $(a,b)\mapsto(b-a,a)$, and it flips the sign of $D$: since $(b-a)a+(b-a)^2=(b-a)b$,

$$\begin{aligned}D(b-a,a)&=a^2-(b-a)\,b\\&=-D(a,b).\end{aligned}$$

Starting from $(8,13)$, where $D=169-104-64=1$, the reverse steps give

$$\begin{aligned}&(8,13)\to(5,8)\to(3,5)\to(2,3)\\&\to(1,2)\to(1,1)\to(0,1),\end{aligned}$$

with $D=1,-1,1,-1,1,-1,1$ along the way. The walk ends at $(F_0,F_1)=(0,1)$ after six steps, and indeed $(8,13)=(F_6,F_7)$.

Claim. If $a,b\ge1$ and $D(a,b)=\pm1$, then $(a,b)=(F_j,F_{j+1})$ for some $j\ge1$, and $D(a,b)=(-1)^j$.

Proof. First, $a\le b\le2a$. If $b\lt a$, then $a\ge2$ and $D=b(b-a)-a^2\lt-a^2\le-4$. If $b\gt2a$, then $b-a\gt a$, and $D=b(b-a)-a^2$ exceeds $2a\cdot a-a^2=a^2\ge1$. Both contradict $D=\pm1$. So one reverse step leads to the pair $(b-a,a)$ with $0\le b-a\le a$, whose value of $D$ is $\mp1$, and the sum of the two entries drops from $a+b$ to $b$. As long as the first entry is positive, the same argument applies again, and since the sum cannot drop forever, after some number $j\ge1$ of steps the first entry is $0$. A pair $(0,c)$ with $D=c^2=\pm1$ is $(0,1)=(F_0,F_1)$. Going forward again, $j$ Fibonacci steps lead from $(F_0,F_1)$ to $(F_j,F_{j+1})$, so $(a,b)=(F_j,F_{j+1})$; and since $D(0,1)=1$ and every step flips the sign, $D(a,b)=(-1)^j$.

The sign rule is Cassini's identity in disguise: $D(F_j,F_{j+1})$ equals $F_{j+1}(F_{j+1}-F_j)-F_j^2$, which is $F_{j+1}F_{j-1}-F_j^2=(-1)^j$. ^[5]

7. Only even indices survive

By Section 5 a golden nugget is a product $pq$ of positive integers with $D(p,q)=1$. By Section 6, $(p,q)=(F_j,F_{j+1})$ with $(-1)^j=1$, so $j=2k$ is even, with $k\ge1$. As $1-x-x^2=D(p,q)/q^2$ for $x=p/q$, the sign of $D$ also tells on which side of $1/\varphi$ a ratio of neighbouring Fibonacci numbers lies: $\tfrac12$, $\tfrac35$, $\tfrac8{13}$ below, and $\tfrac11$, $\tfrac23$, $\tfrac58$ above, where the series diverges.

8. The golden nuggets

Theorem. The golden nuggets are exactly the numbers $G_k=F_{2k}F_{2k+1}$ with $k\ge1$, and $G_k$ is the value of the series at $x=F_{2k}/F_{2k+1}$. Both factors grow with $k$, so $G_1\lt G_2\lt G_3\lt\cdots$, and $G_k$ is the $k$-th golden nugget.

Section 7 shows that every nugget has this form, and Section 5 shows that every $G_k$ is a nugget, because $D(F_{2k},F_{2k+1})=1$. For $k=3$ and $x=\tfrac8{13}$, for example, $1-x-x^2$ equals $(169-104-64)/169=1/169$, so $A_F(x)=\tfrac8{13}\cdot169=104$. The first seven products are the nuggets found by the search of Section 4, and the next three are $987\cdot1597=1576239$, $2584\cdot4181=10803704$ and $6765\cdot10946=74049690$, the $10$th nugget given in the statement.

9. A check through the discriminant

By Section 3, $5n^2+2n+1$ must be a perfect square for every nugget $n$. For $n=pq$ with $D=q^2-pq-p^2=1$ we may write $5n^2+2n+1$ as $5p^2q^2+2pqD+D^2$, and expanding gives

$$5p^2q^2+2pqD+D^2=(p^2+q^2)^2.$$

With $p=F_{2k}$ and $q=F_{2k+1}$, the identity $F_{m-1}^2+F_m^2=F_{2m-1}$ ^[2] turns $p^2+q^2$ into $F_{4k+1}$. So the square roots are $F_5=5$, $F_9=34$, $F_{13}=233$, …; for $k=2$, $5\cdot15^2+2\cdot15+1=1156=34^2$, and the formula of Section 3 returns $(-16+34)/30=\tfrac35$.

Multiplying $m^2=5n^2+2n+1$ by $5$ and completing the square gives $(5n+1)^2-5m^2=-4$, a generalized Pell equation. ^[6] The Lucas numbers $L_0=2$, $L_1=1$, $L_t=L_{t-1}+L_{t-2}$ satisfy $L_t^2-5F_t^2=4(-1)^t$, ^[7] so every odd $t$ gives a solution $(L_t,F_t)$. Modulo $5$ they repeat $2,1,3,4$, because $L_4=7$ and $L_5=11$ leave the remainders of $L_0$ and $L_1$, so the condition $5n+1\equiv1\pmod5$ picks out $t\equiv1\pmod4$; indeed $5G_k+1=L_{4k+1}$, for example $11=L_5$, $76=L_9$ and $521=L_{13}$. The theory of Pell equations is not needed here, because Sections 5 to 7 already prove that the list of nuggets is complete.

10. How fast the nuggets grow

Binet's formula $F_t=(\varphi^t-\psi^t)/\sqrt5$ with $\psi=(1-\sqrt5)/2=-1/\varphi$ ^[2] and its companion $L_t=\varphi^t+\psi^t$ ^[7] give, because $\varphi\psi=-1$ and $\varphi+\psi=1$,

$$\begin{aligned}5G_k&=(\varphi^{2k}-\psi^{2k})(\varphi^{2k+1}-\psi^{2k+1})\\&=\varphi^{4k+1}+\psi^{4k+1}\\&\quad-(\varphi\psi)^{2k}(\varphi+\psi)\\&=L_{4k+1}-1.\end{aligned}$$

Since $|\psi|\lt1$, the nugget $G_k$ is very close to $(\varphi^{4k+1}-1)/5$, and consecutive nuggets differ by a factor that tends to $\varphi^4=(7+3\sqrt5)/2\approx6.854$: the ratios $G_{k+1}/G_k$ begin $7.5$, $6.933$, $6.865$, $6.856$, $6.854$. This is why the nuggets become rarer: below a bound $X$ there are only about $\log X/\log\varphi^4$ of them. The numbers $\varphi^4$ and $\psi^4$ are the roots of $z^2-7z+1$, so $L_{t+8}=7L_{t+4}-L_t$, and with $L_{4k+1}=5G_k+1$ this becomes the recurrence

$$G_{k+1}=7G_k-G_{k-1}+1,$$

valid for $k\ge1$ with $G_0=0$ and $G_1=2$; for example $7\cdot15-2+1=104$. ^[8]

How the Code Works

None of the three programs evaluates the series or searches for $x$: they compute $G_k=F_{2k}F_{2k+1}$ from Section 8. The C++ program ^[9] keeps its settings in the structure Options, with index $=15$ and run_checkpoints set to true. parse_arguments accepts --skip-checkpoints and --index= followed by digits, which parse_int_after_prefix accumulates in an int without an overflow check, so a value above $2^{31}-1$ has undefined behaviour. Any other argument is reported as unknown on standard error and, like an index below $1$, ends the program with exit code $1$.

nth_nugget(index) sets need to $2k+1$ for $k=$ index and starts from f0 $=F_0=0$ and f1 $=F_1=1$. The loop with counter $i=2,3,\dots,$ need forms f2 = f0 + f1 and shifts the pair, so after the pass with counter $i$ the pair is $(F_{i-1},F_i)$. After the last pass it is $(F_{2k},F_{2k+1})$, and the function returns the product $G_k$; for the default index the loop makes $30$ passes. The variables have the type u128, an alias for the GCC extension unsigned __int128, which Clang also accepts. ^[10] The standard streams cannot print this type, so to_string_u128 collects the decimal digits by repeated division by $10$ and reverses them. run_checkpoints requires nth_nugget(3) to be $104$, the worked example of Section 8, and otherwise ends the program with exit code $2$; then main prints nth_nugget(index).

The 128-bit type holds $G_k$ for every $k\le46$, far beyond the default index (even 64 bits would suffice for $k\le23$), while $G_{47}$ exceeds $2^{128}$. Unsigned arithmetic wraps around silently, so for $47\le k\le2^{30}-2$ the program prints $G_k\bmod2^{128}$ instead of $G_k$, without a warning. Larger indices overflow the signed int arithmetic of 2 * index + 1 or of the loop counter, which is undefined behaviour.

The Python version has the index $15$ built in, without options or a checkpoint; solve runs the same loop with the tuple assignment f0, f1 = f1, f0 + f1 over range(2, need + 1) and prints f0 * f1. The Java version does the same in main with BigInteger values and the methods add and multiply. Python integers and Java's BigInteger have arbitrary precision, so the Fibonacci values cannot wrap around as in C++; Java's int loop bounds are harmless at the fixed index. ^[11]

Complexity and Verification

For index $k$ the loop makes $2k$ additions, followed by one multiplication. In C++ each of them is a single operation on 128-bit numbers, so the time is $O(k)$ and the memory $O(1)$. In Python and Java, $F_j$ has about $0.694\,j$ bits, since $\log_2\varphi\approx0.694$, so the numbers take $O(k)$ bits of memory, the additions cost $O(k^2)$ bit operations in total, and the final multiplication costs at most $O(k^2)$ more; at the built-in index the loop has only $30$ passes. For a huge index the doubling formulas $F_{2m}=F_m(2F_{m+1}-F_m)$ and $F_{2m+1}=F_m^2+F_{m+1}^2$ would reach $F_{2k}$ and $F_{2k+1}$ with $O(\log k)$ multiplications. ^[2] A search over $n$ as in Section 4 would be hopeless, because every further nugget multiplies the range by about $6.854$.

The C++ program checks itself with $G_3=104$. Separate checks for this article, not part of the published solutions, confirmed the following. The perfect-square test of Section 3 for every $n\le10^6$ finds exactly the seven nuggets of Section 4. An exhaustive search over all fractions $p/q$ in lowest terms with $q\le3000$ and $0\lt p/q\lt1/\varphi$ finds an integer value only at the eight fractions $F_{2k}/F_{2k+1}$ with $k\le8$, each with $q^2-pq-p^2=1$. For every $a\le10^6$, solving $b^2-ab-a^2=\pm1$ for $b$ gives only the pairs $(F_j,F_{j+1})$, with the sign $(-1)^j$. Exact rational arithmetic confirms $A_F(F_{2k}/F_{2k+1})=G_k$ through the fraction of Section 1 for $k\le60$, and the identities of Sections 9 and 10 hold for $k\le90$. The C++ program, compiled with GCC and with Clang, and the Python and Java programs print the same number, which equals the value of the recurrence of Section 10, and --index=$k$ gives the exact $G_k$ for $k\le46$ and $G_k\bmod2^{128}$ for $47\le k\le60$.

Footnotes and References

The references below supply the background facts used above. The reduction to $q^2-pq-p^2=1$, the descent of Section 6 and the checks of the code are derived explicitly in this article.

Project Euler 137 — Fibonacci Golden Nuggets. The official statement defines A_F(x) = xF₁ + x²F₂ + x³F₃ + … for the Fibonacci numbers, shows that A_F(1/2) = 2, lists the x with A_F(x) = 1, 2, 3, 4, 5, calls A_F(x) a golden nugget when x is rational, gives the 10th golden nugget 74049690 and asks for the 15th.
Wikipedia — Fibonacci sequence. The ordinary generating function of the Fibonacci numbers is z/(1 − z − z²), convergent for |z| < 1/φ ≈ 0.618. The article also gives Binet's formula Fₙ = (φⁿ − ψⁿ)/√5 and the doubling formulas F₂ₙ = (2Fₙ₊₁ − Fₙ)Fₙ and F₂ₙ₋₁ = Fₙ² + Fₙ₋₁², which compute Fibonacci numbers recursively in O(log n) arithmetic operations.
Wikipedia — Irrational number. All square roots of natural numbers other than perfect squares are irrational.
Wikipedia — Euclid's lemma. If a prime p divides the product ab of two integers a and b, then p divides a or b.
Wikipedia — Cassini and Catalan identities. Cassini's identity Fₙ₋₁Fₙ₊₁ − Fₙ² = (−1)ⁿ, with a proof by a matrix determinant and one by induction.
Wikipedia — Pell's equation. The equation x² − cy² = N in integers x, y, with a fixed positive non-square integer c and a fixed integer N, is called the generalized Pell equation; (5n + 1)² − 5m² = −4 in Section 9 is the case c = 5, N = −4.
MathWorld — Lucas Number. The Lucas numbers satisfy Lₙ = Lₙ₋₁ + Lₙ₋₂ with L₁ = 1 and L₂ = 3, the Binet form Lₙ = ((1 + √5)/2)ⁿ + ((1 − √5)/2)ⁿ and the identity Lₙ² − 5Fₙ² = 4(−1)ⁿ.
OEIS A081018. The sequence a(n) = (Lucas(4n + 1) − 1)/5 = Fibonacci(2n)·Fibonacci(2n + 1); a comment describes its terms as the nonnegative integers k with G(x) = k for some rational x, where G(x) = x/(1 − x − x²) is the generating function of the Fibonacci numbers, and a formula gives 0 = a(n) − 7a(n + 1) + a(n + 2) − 1.
C++ — Euler137.cpp. The linked immutable C++ revision contains parse_arguments, nth_nugget, to_string_u128 and run_checkpoints with the checkpoint 104. It is the implementation record for this article.
GCC manual — 128-bit Integers. As an extension, GCC supports the integer types __int128 and unsigned __int128 on targets that have an integer mode wide enough to hold 128 bits.
Java — BigInteger: immutable arbitrary-precision integers. Python — numeric types: integers have unlimited precision.

Problem 137 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u128 = unsigned __int128;

struct Options {
    int index = 15;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--index=", options.index)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.index >= 1;
}

u128 nth_nugget(const int index) {
    const int need = 2 * index + 1;

    u128 f0 = 0;
    u128 f1 = 1;
    for (int i = 2; i <= need; ++i) {
        const u128 f2 = f0 + f1;
        f0 = f1;
        f1 = f2;
    }

    const u128 f_2n = f0;
    const u128 f_2n1 = f1;
    return f_2n * f_2n1;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

bool run_checkpoints() {
    if (to_string_u128(nth_nugget(3)) != "104") {
        std::cerr << "Checkpoint failed for index=3" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << to_string_u128(nth_nugget(options.index)) << '\n';
    return 0;
}

Python

# Problem 137: Fibonacci golden nuggets
# The n-th golden nugget is F(2n) * F(2n+1).

def solve():
    index = 15
    need = 2 * index + 1
    f0, f1 = 0, 1
    for _ in range(2, need + 1):
        f0, f1 = f1, f0 + f1
    print(f0 * f1)

solve()

Java

import java.math.BigInteger;

public class Euler137 {
    public static void main(String[] args) {
        int index = 15, need = 2 * index + 1;
        BigInteger f0 = BigInteger.ZERO, f1 = BigInteger.ONE;
        for (int i = 2; i <= need; i++) {
            BigInteger f2 = f0.add(f1);
            f0 = f1;
            f1 = f2;
        }
        System.out.println(f0.multiply(f1));
    }
}