Problem 140: Modified Fibonacci Golden Nuggets

Mathematical Foundation

Theorem 1. Setting $A_G(x) = n$ yields the quadratic $(n+3)x^2 + (n+1)x - n = 0$, whose discriminant is $D = 5n^2 + 14n + 1$.

Proof. From $n = \frac{x + 3x^2}{1 - x - x^2}$: $n(1 - x - x^2) = x + 3x^2$, hence $(n+3)x^2 + (n+1)x - n = 0$. The discriminant is:

$\square$

Theorem 2. The condition $5n^2 + 14n + 1 = k^2$ (for $n$ to be a golden nugget) reduces to the generalized Pell equation $a^2 - 5k^2 = 44$, where $a = 5n + 7$.

Proof. Multiplying $5n^2 + 14n + 1 = k^2$ by 5:

Setting $a = 5n + 7$ gives $a^2 - 5k^2 = 44$. For $n$ to be a positive integer, we need $a > 7$ and $a \equiv 2 \pmod{5}$ (since $5n + 7 \equiv 2 \pmod{5}$). $\square$

Lemma 1. The fundamental solutions of $a^2 - 5b^2 = 44$ (with $a, b > 0$) are:

Proof. We search for $a > 0$ with $a^2 \equiv 44 \pmod{5}$, i.e., $a^2 \equiv 4 \pmod{5}$, so $a \equiv \pm 2 \pmod{5}$. Testing small values:

• $a = 2$: $4 - 5b^2 = 44 \Rightarrow b^2 = -8$. No.
• $a = 3$: $9 - 5b^2 = 44 \Rightarrow b^2 = -7$. No.
• $a = 7$: $49 - 5b^2 = 44 \Rightarrow b^2 = 1 \Rightarrow b = 1$. Yes.
• $a = 8$: $64 - 5b^2 = 44 \Rightarrow b^2 = 4 \Rightarrow b = 2$. Yes.
• $a = 12$: $144 - 5b^2 = 44 \Rightarrow b^2 = 20$. No.
• $a = 13$: $169 - 5b^2 = 44 \Rightarrow b^2 = 25 \Rightarrow b = 5$. Yes.
• $a = 17$: $289 - 5b^2 = 44 \Rightarrow b^2 = 49 \Rightarrow b = 7$. Yes.

Further solutions are generated from these by the automorphism of the Pell equation. $\square$

Theorem 3. Each fundamental solution generates an infinite family via the recurrence using the fundamental solution $(9, 4)$ of $u^2 - 5v^2 = 1$:

All solution chains are generated from fundamental solutions $(a_0, b_0)$ and their negatives $(-a_0, -b_0)$.

Proof. If $(a, b)$ solves $a^2 - 5b^2 = 44$ and $(u, v)$ solves $u^2 - 5v^2 = 1$, then $(au + 5bv, av + bu)$ also solves $a^2 - 5b^2 = 44$ (by the multiplicativity of the Pell norm). Taking $(u, v) = (9, 4)$ gives the stated recurrence. Starting from negative fundamentals $(-a_0, -b_0)$ produces additional chains that eventually yield positive $(a, b)$ with $a > 7$. $\square$

Lemma 2. The golden nuggets are obtained by filtering: from each chain, select solutions where $a > 7$ and $a \equiv 2 \pmod{5}$. The resulting $n = (a - 7)/5$.

Proof. Direct from Theorem 2. $\square$

Editorial

G(x) = x(1+3x)/(1-x-x^2). Find sum of first 30 golden nuggets. Reduces to generalized Pell equation a^2 - 5*b^2 = 44 where a = 5n + 7. We fundamental solutions and their negatives. We then generate solutions along this chain. Finally, advance: (a, b) -> (9a + 20b, 4a + 9b).

Pseudocode

count = 30
Fundamental solutions and their negatives
Generate solutions along this chain
Advance: (a, b) -> (9a + 20b, 4a + 9b)

Complexity Analysis

• Time: $O(C \cdot I)$ where $C = 8$ chains and $I \approx 50$ iterations per chain. Each iteration is $O(1)$ arithmetic (with big integers, $O(i)$ bits at step $i$).
• Space: $O(\text{count})$ to store and sort the nuggets.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Solve a^2 - 5*b^2 = 44
    // Fundamental solutions: (7,1), (8,2), (13,5), (17,7)
    // Recurrence: (a,b) -> (9a+20b, 4a+9b)
    // Need a > 7 and a % 5 == 2, then n = (a-7)/5

    vector<pair<long long, long long>> fund = {
        {7, 1}, {8, 2}, {13, 5}, {17, 7}
    };

    set<long long> nuggets;

    // Try all sign combinations for fundamental solutions
    for (auto [a0, b0] : fund) {
        vector<pair<long long, long long>> starts = {
            {a0, b0}, {-a0, -b0}, {-a0, b0}, {a0, -b0}
        };
        for (auto [sa, sb] : starts) {
            long long a = sa, b = sb;
            for (int iter = 0; iter < 40; iter++) {
                if (a > 7 && (a - 7) % 5 == 0) {
                    long long n = (a - 7) / 5;
                    if (n > 0) nuggets.insert(n);
                }
                long long na = 9 * a + 20 * b;
                long long nb = 4 * a + 9 * b;
                a = na;
                b = nb;
            }
        }
    }

    // Sum first 30
    long long sum = 0;
    int count = 0;
    for (long long n : nuggets) {
        if (count >= 30) break;
        sum += n;
        count++;
    }

    cout << sum << endl;
    return 0;
}

"""
Problem 140: Modified Fibonacci Golden Nuggets

G(x) = x(1+3x)/(1-x-x^2). Find sum of first 30 golden nuggets.

Reduces to generalized Pell equation a^2 - 5*b^2 = 44 where a = 5n + 7.
"""

def solve():
    fund = [(7, 1), (8, 2), (13, 5), (17, 7)]
    nuggets = set()

    for a0, b0 in fund:
        for sa, sb in [(a0, b0), (-a0, -b0), (-a0, b0), (a0, -b0)]:
            a, b = sa, sb
            for _ in range(40):
                if a > 7 and (a - 7) % 5 == 0:
                    n = (a - 7) // 5
                    if n > 0:
                        nuggets.add(n)
                a, b = 9 * a + 20 * b, 4 * a + 9 * b

    sorted_nuggets = sorted(nuggets)[:30]
    return sum(sorted_nuggets)

if __name__ == "__main__":
    answer = solve()
assert answer == 5673835352990
print(answer)