Problem 140: Modified Fibonacci Golden Nuggets

Project Euler Problem 140 Solution

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

Problem Summary Let $G_1=1$, $G_2=4$, and $G_k=G_{k-1}+G_{k-2}$ for $k\ge 3$. The generating function is $$A_G(x)=\sum_{k=1}^{\infty} G_k x^k.$$ A "golden nugget" is a positive integer $n$ for which the equation $A_G(x)=n$ has a positive rational solution $x$. The task is to add the first 30 such integers. The crucial point is that this is not a search over rational numbers. After simplifying the generating function, the nugget condition becomes a Pell-type Diophantine equation, and the implementations generate all relevant solutions from a small set of seed pairs. Mathematical Approach The sequence begins $1,4,5,9,14,23,\dots$, so the same Fibonacci recurrence is present, but the initial values are different. That changes the numerator of the generating function and, later, the constant term in the Pell equation. From the recurrence to a closed generating function Write $A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k$. Using $G_k=G_{k-1}+G_{k-2}$, $$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$ Reindex the two sums: $$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$ Therefore $$A_G(x)(1-x-x^2)=x+3x^2,$$ so the generating function is $$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}.}$$ The rationality condition becomes a square discriminant Set $A_G(x)=n$ with $n\in \mathbb Z_{>0}$....

Detailed mathematical approach

Problem Summary

The numbers $G_1=1$, $G_2=4$ and $G_k=G_{k-1}+G_{k-2}$ for $k\ge3$ form the sequence $1,4,5,9,14,23,\dots$, and

$$A_G(x)=xG_1+x^2G_2+x^3G_3+\cdots$$

is the power series with these coefficients. We look at the values of $x$ for which $A_G(x)$ is a positive integer; when such an $x$ is rational, the integer $A_G(x)$ is called a golden nugget. The statement lists the values of $x$ that give $A_G(x)=1,2,3,4,5$: they are $(\sqrt5-1)/4$, $2/5$, $(\sqrt{22}-2)/6$, $(\sqrt{137}-5)/14$ and $1/2$, so $2$ and $5$ are golden nuggets, while $1$, $3$ and $4$ are not. It adds that the nuggets become increasingly rare and that the $20$th golden nugget is $211345365$. We must find the sum of the first thirty golden nuggets. ^[1]

The whole solution in one sentence: the series has a simple closed form, so $A_G(x)=n$ becomes a quadratic equation whose root $x$ is rational exactly when $5n^2+14n+1$ is a perfect square, and all whole-number solutions of this condition grow out of six small starting pairs by repeating one simple step, so the nuggets can be listed in increasing order without any search.

Mathematical Approach

We sum the series, turn the condition that $x$ is rational into an equation of Pell type in whole numbers, and find all its solutions with a step that never leaves the set of solutions.

1. Summing the series

Multiply the series by $1-x-x^2$. The coefficient of $x^k$ in the product is $G_k-G_{k-1}-G_{k-2}$, which is $0$ for every $k\ge3$ by the recurrence; only $x$, with coefficient $G_1=1$, and $x^2$, with coefficient $G_2-G_1=3$, survive. Hence

$$A_G(x)=\frac{x+3x^2}{1-x-x^2}.$$

For $x=1/2$ the terms are $\tfrac12+1+\tfrac58+\tfrac9{16}+\tfrac7{16}+\cdots$, and the formula gives $(\tfrac12+\tfrac34)/\tfrac14=5$, the value in the statement. The formula holds only where the series converges. With the Fibonacci numbers $F_0=0$, $F_1=1$, $F_{k+1}=F_k+F_{k-1}$ we have $G_k=F_k+3F_{k-1}$, because both sides start with $1,4$ and follow the same rule. The ratio $F_{k+1}/F_k$ tends to the golden ratio $\varphi=(1+\sqrt5)/2\approx1.618$, ^[2] so $G_{k+1}/G_k$ does too, and by the ratio test the series converges for $|x|\lt1/\varphi$ and diverges for $|x|\gt1/\varphi$. At $|x|=1/\varphi$ it diverges too: $G_k\ge\varphi^{k-1}$, by induction from $G_1=1$, $G_2=4\gt\varphi$ and $\varphi^2=\varphi+1$, so the terms do not tend to $0$. Here $1/\varphi=(\sqrt5-1)/2\approx0.618$ is the positive root of the denominator.

2. One value of x for every n

For $0\lt x\lt1/\varphi$ all terms are positive, so $A_G$ increases from $A_G(0)=0$, and it tends to infinity as $x$ approaches $1/\varphi$, where the denominator vanishes. Every positive integer $n$ is therefore the value $A_G(x)$ at exactly one $x$ in this interval. Negative $x$ give no positive integers: for $-1/\varphi\lt x\lt0$ the denominator is positive and $A_G(x)\lt1$, because $x+3x^2\lt1-x-x^2$ means $4x^2+2x-1\lt0$, which holds for every $x$ between $-(1+\sqrt5)/4\approx-0.809$ and $(\sqrt5-1)/4\approx0.309$.

Clearing the denominator in $A_G(x)=n$ gives the quadratic equation

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

The product of its two roots is $-n/(n+3)\lt0$, so exactly one root is positive, namely

$$\begin{aligned}x&=\frac{-(n+1)+\sqrt{D}}{2(n+3)},\\ D&=5n^2+14n+1,\end{aligned}$$

where $D=(n+1)^2+4n(n+3)$ is the discriminant. This root lies in the interval of convergence: it satisfies $n(1-x-x^2)=x+3x^2\gt0$, so $1-x-x^2\gt0$ and $x\lt1/\varphi$. The table of the statement follows: $n=1,2,3,4,5$ give $D=20,49,88,137,196$ and $x=(\sqrt{20}-2)/8=(\sqrt5-1)/4$, $x=(7-3)/10=2/5$, $x=(\sqrt{88}-4)/12$${}=(\sqrt{22}-2)/6$, $x=(\sqrt{137}-5)/14$ and $x=(14-6)/16=1/2$.

3. Rational x means a square

The root $x$ is rational exactly when $\sqrt D=2(n+3)x+n+1$ is rational, and the square root of a whole number is rational only if it is a whole number: if $\sqrt D=p/q$ in lowest terms, then $Dq^2=p^2$, so every prime factor of $q$ divides $p$, and $q=1$. So $n$ is a golden nugget exactly when

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

for some whole number $m$. For $n=1,\dots,6$ the values of $D$ are $20,49,88,137,196,265$, with the squares $49=7^2$ and $196=14^2$ at the nuggets $2$ and $5$; the next square is $D=2500=50^2$ at $n=21$. Testing every $n$ finds the first nuggets, but they grow exponentially (Section 9), so a search for thirty would have to cover an enormous range.

4. A Pell-type equation

Multiplying $D=m^2$ by $5$ and completing the square, $5D=25n^2+70n+5$${}=(5n+7)^2-44$, turns the condition into

$$X^2-5Y^2=44$$

with $X=5n+7$ and $Y=m$. For example, $n=2$ belongs to $(X,Y)=(17,7)$, since $289-245=44$, and $n=5$ to $(32,14)$, since $1024-980=44$. An equation $x^2-dy^2=N$ with a positive non-square $d$ is a generalized Pell equation; all its solutions are finitely many of them multiplied by solutions of the ordinary Pell equation $a^2-db^2=1$. ^[3]

To go back to $n$ we need $X\equiv2\pmod5$, read "$X$ is congruent to $2$ modulo $5$": $X$ leaves the remainder $2$ on division by $5$. Such congruences may be added and multiplied like equations. ^[4] A solution in positive integers with $X\equiv2\pmod5$ and $X\gt7$ gives the nugget $n=(X-7)/5\ge1$, because then $D=(X^2-44)/5=Y^2$.

5. A step that keeps the equation

Brahmagupta's identity, which can be checked by expanding both sides, ^[5]

$$\begin{aligned}&(X^2-5Y^2)(a^2-5b^2)\\ &\quad=(aX+5bY)^2-5(bX+aY)^2,\end{aligned}$$

shows how to make new solutions from old ones. The smallest positive solution of $a^2-5b^2=1$ is $(a,b)=(9,4)$, because $81-80=1$, ^[3] and with it the identity says that the step

$$(X,Y)\mapsto(9X+20Y,\;4X+9Y)$$

turns every solution of $X^2-5Y^2=44$ into another one. For example, $(7,1)$ becomes $(83,37)$, and indeed $83^2-5\cdot37^2=6889-6845=44$. In the language of the numbers $X+Y\sqrt5$, the step is multiplication by $u=9+4\sqrt5\approx17.94$. Its inverse, the step $(X,Y)\mapsto(9X-20Y,\;9Y-4X)$, is multiplication by $9-4\sqrt5=1/u$ and keeps the equation as well.

6. Six chains contain every solution

Call the six smallest positive solutions

$$\begin{aligned}&(7,1),\ (8,2),\ (13,5),\\ &(17,7),\ (32,14),\ (43,19)\end{aligned}$$

the seeds, and the sequence that the step of Section 5 produces from a seed its chain; the seed is the member at position $k=0$. The key claim is that every solution in positive integers lies in exactly one chain, at exactly one position. To prove it, take a positive solution $(X,Y)$, so $X^2=5Y^2+44$, and apply the inverse step, $(X',Y')=(9X-20Y,\;9Y-4X)$:

$X'\gt0$, because $81X^2=405Y^2+3564\gt400Y^2$;
$Y'\lt Y$, because $X^2\gt4Y^2$ gives $X\gt2Y$, and so $9Y-4X\lt Y$;
$Y'\gt0$ exactly when $81Y^2\gt16X^2=80Y^2+704$, that is, when $Y^2\gt704$, or $Y\ge27$.

So as long as $Y\ge27$, the inverse step leads to another positive solution with a smaller $Y$. This cannot go on forever, so we arrive at a positive solution with $Y\le26$. Checking $Y=1,2,\dots,26$ shows that $5Y^2+44$ is a square only for $Y=1,2,5,7,14,19$, which gives exactly the six seeds. In the other direction, the step increases $Y$, and one step already turns the seeds into solutions with $Y=37,50,97,131,254,343$, all at least $27$. So no seed appears again later in a chain, and going back from the member at position $k$ of a chain reaches its seed after exactly $k$ inverse steps. This proves the claim.

This is a concrete case of a general theorem: ^[6] for $N\gt0$, every integer solution of $x^2-dy^2=N$ is $(x_0+y_0\sqrt d)\,u^k$ with an integer $k$ and a solution $(x_0,y_0)$ with

$$|y_0|\le\frac{\sqrt N\,\bigl(\sqrt u-1/\sqrt u\bigr)}{2\sqrt d}.$$

Here $\sqrt u=2+\sqrt5$ gives $\sqrt u-1/\sqrt u=4$ and the bound $2\sqrt{44/5}\approx5.93$, which leaves $(\pm7,\pm1)$, $(\pm8,\pm2)$ and $(\pm13,\pm5)$; the step turns $(13,-5)$, $(8,-2)$ and $(7,-1)$ into the seeds $(17,7)$, $(32,14)$ and $(43,19)$.

7. Every second member is a nugget

Modulo $5$ the equation says $X^2\equiv44\equiv4$. The squares of $0,1,2,3,4$ leave the remainders $0,1,4,4,1$, so $X\equiv2$ or $X\equiv3\pmod5$, and only $X\equiv2$ gives a nugget. The step changes $X$ into $9X+20Y\equiv4X\equiv-X\pmod5$, so along every chain the remainder alternates: $2,3,2,3,\dots$ or $3,2,3,2,\dots$. The seeds $7$, $17$ and $32$ have the remainder $2$, and $8$, $13$ and $43$ have the remainder $3$. Hence the chains of $(7,1)$, $(17,7)$ and $(32,14)$ give nuggets at the even positions $k=0,2,4,\dots$, and the other three chains at the odd positions. The one exception is the seed $(7,1)$ itself: it gives $n=0$, the trivial value $A_G(0)=0$ at $x=0$, which is not positive. This is why the test $X\gt7$ is needed besides $X\equiv2\pmod5$.

8. Worked example: the first eight nuggets

The first three members of each chain, with the nuggets $n=(X-7)/5$ of the members whose remainder is $2$, are:

$(7,1)$: $X=7,83,1487$, giving $n=0$, which is not counted, and $n=296$;
$(8,2)$: $X=8,112,2008$, giving $n=21$;
$(13,5)$: $X=13,217,3893$, giving $n=42$;
$(17,7)$: $X=17,293,5257$, giving $n=2$ and $n=1050$;
$(32,14)$: $X=32,568,10192$, giving $n=5$ and $n=2037$;
$(43,19)$: $X=43,767,13763$, giving $n=152$.

In increasing order the first eight nuggets are $2,5,21,42,152,296,1050,2037$, and the first five add up to $222$. Let us follow $n=21$ all the way. The step sends $(8,2)$ to $(9\cdot8+20\cdot2,\;4\cdot8+9\cdot2)$${}=(112,50)$, and $112^2-5\cdot50^2$${}=12544-12500=44$. Then $n=(112-7)/5=21$ and $D=5\cdot441+294+1$${}=2500=50^2$. The quadratic equation $24x^2+22x-21=0$ has the positive root $x=(-22+50)/48=7/12$, and indeed

$$\begin{aligned}A_G\Bigl(\frac7{12}\Bigr)&=\frac{\frac7{12}+\frac{147}{144}}{1-\frac7{12}-\frac{49}{144}}\\ &=\frac{231/144}{11/144}=21.\end{aligned}$$

The values of $x$ for the eight nuggets are $2/5$, $1/2$, $7/12$, $3/5$, $19/31$, $8/13$, $50/81$ and $21/34$. They creep up towards $1/\varphi\approx0.618$, and $1/2$, $3/5$, $8/13$ and $21/34$ are ratios of consecutive Fibonacci numbers.

9. The order of the nuggets and their growth

For a positive solution write $\alpha=X+Y\sqrt5$. Its partner $X-Y\sqrt5$ equals $44/\alpha$, so $X=(\alpha+44/\alpha)/2$, which grows with $\alpha$ once $\alpha\gt\sqrt{44}\approx6.63$; every positive solution has $\alpha\ge7+\sqrt5\approx9.24$. Ordering the solutions by $X$ is therefore the same as ordering them by $\alpha$. The six seeds have $\alpha$ between $9.24$ and $43+19\sqrt5\approx85.49$, below $u\,(7+\sqrt5)\approx165.73$, and the step multiplies $\alpha$ by $u$. So if block $k$ means the six members at position $k$ of the chains, every member of block $k$ is smaller than every member of block $k+1$, and within each block the chains keep the order of their seeds. By Section 7, block $0$ contains two nuggets and every later block three, so the first $30$ nuggets are the nuggets of blocks $0$ to $9$ and the first nugget of block $10$: the first $11$ members of each chain are enough.

Since $\varphi^6=8\varphi+5=9+4\sqrt5$, ^[2] the step multiplies $\alpha$ by $u=\varphi^6$. Two blocks hold six nuggets, so the ratio of a nugget to the one six places earlier tends to $u^2=161+72\sqrt5\approx322$, and the growth per nugget is $(u^2)^{1/6}=\varphi^2\approx2.618$ in the geometric mean; the single ratios alternate and tend to about $1.94$ and $3.54$. This is the precise sense in which the nuggets become rarer.

10. A finer step

Since $X^2-Y^2=44+4Y^2$ is even, $X$ and $Y$ have the same parity, so multiplication by $\varphi^2=(3+\sqrt5)/2$ also gives whole numbers,

$$(X,Y)\mapsto\Bigl(\frac{3X+5Y}2,\;\frac{X+3Y}2\Bigr),$$

and keeps the equation, by Brahmagupta's identity with $a=3/2$ and $b=1/2$. Three such steps make one step by $u=\varphi^6$, and the six seeds lie on just two finer chains, with $X=7,13,32,83,\dots$ and $X=8,17,43,112,\dots$. They alternate in size, since $7+\sqrt5\lt8+2\sqrt5$${}\lt13+5\sqrt5$${}=\varphi^2(7+\sqrt5)$, and together they give sequence A228210 of the OEIS. ^[7] The remainder modulo $5$ alternates along them too, so the nuggets alternate between the two chains, and two finer steps forwards or backwards turn $X$ into $(7X\pm15Y)/2$, which add up to $7X$. With $n=(X-7)/5$ the $k$th nugget $g_k$ therefore satisfies

$$g_k=7g_{k-2}-g_{k-4}+7\qquad(k\ge5),$$

for example $7\cdot21-2+7=152$ and $7\cdot42-5+7=296$. The published programs use the coarser step with six seeds.

How the Code Works

The C++ program ^[8] starts in main: parse_arguments reads --count=K, the number of nuggets to add (default $30$), and --skip-checkpoints, and invalid options end the program with exit code $1$. Unless the checks are skipped, run_checkpoints requires solve(5) to return $222$, the sum from Section 8, or the program stops with exit code $2$; then main prints solve(count). solve walks $50$ steps along the chain of each seed of Section 6. At every member, positions $0$ to $49$, it applies the test of Section 7, x > 7 && (x - 7) % 5 == 0, and inserts $(x-7)/5$ into a std::set; then it applies the step of Section 5, next_x = 9 * x + 20 * y and next_y = 4 * x + 9 * y. Finally it copies the set into a vector, sorts it again, although a set is already sorted, and adds the first count values; the set would also remove duplicates, but by Section 6 the chains never meet. Python does the same with a set and sorted; Java keeps the values in a TreeSet<Long>, which is sorted, and adds the first $30$ while iterating over it. Neither has options or a checkpoint.

The programs go to $50$ members per chain instead of the $11$ of Section 9, and there the languages differ. Python integers have unlimited precision, so all steps are exact; the largest member tested has $64$ digits. ^[9] The C++ type i64 and the Java type long stop at $2^{63}-1\approx9.2\cdot10^{18}$, so the members are exact only up to position $k=14$, or $k=13$ in the chains of $(32,14)$ and $(43,19)$; later steps overflow. Java defines the result: it wraps around silently. ^[9] In C++ signed overflow is undefined behaviour, ^[10] so the language guarantees nothing here, even for the default count; the GCC and Clang builds we tested wrapped around like Java. Under this wrap-around, $14$ wrong values pass the test of Section 7, all larger than the first $39$ true nuggets, which are exact, so the first $30$ values of the set are right, and their sum fits easily in 64 bits. With --count=40 or more the C++ program would add wrong values, and a count above $57$, the size of its set, would read past the end of the vector.

Complexity and Verification

With $L$ members per chain, a run makes $6L$ steps of four multiplications and two additions; with exact arithmetic it keeps $3L-1$ nuggets, by Section 9 exactly the first $3L-1$, and the set operations bring the cost to $O(L\log L)$ time and $O(L)$ memory. The first $K$ nuggets need $L=\lceil(K+1)/3\rceil$, which is $11$ for $K=30$, on numbers of about $0.42K$ digits, since $\log_{10}\varphi^2\approx0.418$. The programs fix $L=50$: one call of solve makes $300$ steps, the C++ program with its checkpoint $600$, and the Python set ends with $149$ nuggets. Each program finishes within a few hundredths of a second, start-up included.

The C++ checkpoint confirms $2+5+21+42+152=222$. Separate computations for this article, not part of the published solutions, confirmed the following:

the power series of the closed form has the coefficients $G_1,\dots,G_{40}$, and the quadratic formula gives all five rows of the statement's table;
a brute-force search over all $n\le10^9$ for which $5n^2+14n+1$ is a square finds exactly $21$ nuggets, the same as the chains, among them the $20$th nugget $211345365$;
all $30$ positive solutions with $Y\le2\cdot10^6$ lead back to a seed, and their values of $X$ are the first $30$ terms of A228210;
for each of the first $30$ nuggets, exact fractions give a rational $x$ with $0\lt x\lt1/\varphi$ and $A_G(x)=n$;
the recurrence of Section 10 holds for all $149$ nuggets of the Python run;
all three programs print the same number as a separately written exact computation, the C++ program with GCC and Clang at several optimisation levels, and Clang's undefined-behaviour sanitizer reports the overflow in the step.

Footnotes and References

The references below supply the background facts used above; the reduction to $X^2-5Y^2=44$, the descent to the six seeds and Sections 7 to 10 are derived in this article.

Project Euler 140 — Modified Fibonacci Golden Nuggets. The official statement defines Gₖ and A_G(x), lists the x that give A_G(x) = 1, …, 5, calls A_G(x) a golden nugget when x is rational, gives the 20th nugget 211345365 and asks for the sum of the first thirty.
Wikipedia — Fibonacci sequence. The series z/(1 − z − z²) of the Fibonacci numbers converges for |z| < 1/φ ≈ 0.618, the ratios Fₙ₊₁/Fₙ tend to φ, and φⁿ = Fₙφ + Fₙ₋₁, so φ² = φ + 1 and φ⁶ = 8φ + 5.
Wikipedia — Pell's equation. The table of fundamental solutions of x² − ny² = 1 lists (9, 4) for n = 5, and every solution of x² − ny² = N is a Pell multiple of one of finitely many solutions.
Wikipedia — Modular arithmetic. Integers are congruent modulo m when their difference is a multiple of m, and congruence is compatible with addition, subtraction and multiplication.
Wikipedia — Brahmagupta's identity. (a² + nb²)(c² + nd²) = (ac − nbd)² + n(ad + bc)²; with n = −5 this is the identity of Section 5.
Keith Conrad — Pell's Equation, II. Theorem 3.3: for u = a + b√d with a² − db² = 1 and a, b > 0, every integral solution of x² − dy² = n is (x₀ + y₀√d)uᵏ with an integer k and x₀² − dy₀² = n, where for n > 0 one can take |y₀| ≤ √n(√u − 1/√u)/(2√d).
OEIS A228210 — x-values in the solutions to x² − 5y² = 44. The entry lists 7, 8, 13, 17, 32, 43, 83, 112, … with a(n) = 3a(n − 2) − a(n − 4) and links Project Euler 140.
C++ — Euler140.cpp. The linked immutable revision, with solve and run_checkpoints, is the implementation record for this article.
Java Language Specification, §4.2.2 — Integer Operations. The integer operators do not indicate overflow in any way, and a long ranges from −2⁶³ to 2⁶³ − 1. Python — numeric types: integers have unlimited precision.
cppreference — Arithmetic operators. Under "Overflows": signed integer overflow is undefined behaviour; it may wrap around, trap, saturate or be optimised away.

Problem 140 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <string>
#include <utility>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    int count = 30;
    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, "--count=", options.count)) {
            continue;
        }

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

i64 solve(const int count) {
    std::vector<std::pair<i64, i64>> seeds = {
        {7, 1}, {8, 2}, {13, 5}, {17, 7}, {32, 14}, {43, 19},
    };

    std::set<i64> nuggets;

    for (auto [x0, y0] : seeds) {
        i64 x = x0;
        i64 y = y0;

        for (int step = 0; step < 50; ++step) {
            if (x > 7 && (x - 7) % 5 == 0) {
                nuggets.insert((x - 7) / 5);
            }

            const i64 next_x = 9 * x + 20 * y;
            const i64 next_y = 4 * x + 9 * y;
            x = next_x;
            y = next_y;
        }
    }

    std::vector<i64> values(nuggets.begin(), nuggets.end());
    std::sort(values.begin(), values.end());

    i64 sum = 0;
    for (int i = 0; i < count; ++i) {
        sum += values[static_cast<std::size_t>(i)];
    }
    return sum;
}

bool run_checkpoints() {
    if (solve(5) != 222) {
        std::cerr << "Checkpoint failed for first five nuggets" << '\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 << solve(options.count) << '\n';
    return 0;
}

Python

# Problem 140: Modified Fibonacci golden nuggets
# AG(x) = x*G1 + x^2*G2*... with G=1,4,5,9,14,...
# Golden nuggets from Pell equation seeds, then x=(X-7)/5.

def solve():
    count = 30
    seeds = [(7,1),(8,2),(13,5),(17,7),(32,14),(43,19)]
    nuggets = set()
    for x0, y0 in seeds:
        x, y = x0, y0
        for _ in range(50):
            if x > 7 and (x - 7) % 5 == 0:
                nuggets.add((x - 7) // 5)
            x, y = 9*x + 20*y, 4*x + 9*y
    vals = sorted(nuggets)
    print(sum(vals[:count]))

solve()

Java

import java.util.*;

public class Euler140 {
    public static void main(String[] args) {
        int count = 30;
        long[][] seeds = { { 7, 1 }, { 8, 2 }, { 13, 5 }, { 17, 7 }, { 32, 14 }, { 43, 19 } };
        Set<Long> nuggets = new TreeSet<>();
        for (long[] s : seeds) {
            long x = s[0], y = s[1];
            for (int i = 0; i < 50; i++) {
                if (x > 7 && (x - 7) % 5 == 0)
                    nuggets.add((x - 7) / 5);
                long nx = 9 * x + 20 * y, ny = 4 * x + 9 * y;
                x = nx;
                y = ny;
            }
        }
        long sum = 0;
        int c = 0;
        for (long v : nuggets) {
            if (c >= count)
                break;
            sum += v;
            c++;
        }
        System.out.println(sum);
    }
}