Problem 235: An Arithmetic Geometric Sequence

Mathematical Foundation

Theorem (Closed-Form Summation). For $r \neq 1$, define $n = 5000$. Then

Proof. We split the sum:

The first sum is a geometric series: $\sum_{k=1}^{n} r^{k-1} = (r^n - 1)/(r - 1)$.

For the second sum, differentiate the geometric series identity $\sum_{k=0}^{n} r^k = (r^{n+1} - 1)/(r - 1)$ with respect to $r$:

This is verified by the quotient rule: the numerator of the derivative of $(r^{n+1} - 1)/(r-1)$ is $(n+1)r^n(r-1) - (r^{n+1} - 1) = nr^{n+1} - (n+1)r^n + 1$. Substituting completes the proof. $\square$

Lemma (Existence and Uniqueness of Root). The equation $s(r) = -6 \times 10^{11}$ has a unique solution in $(1, 1.01)$.

Proof. At $r = 1$: $s(1) = \sum_{k=1}^{5000}(900 - 3k) = 900 \cdot 5000 - 3 \cdot \frac{5000 \cdot 5001}{2} = 4\,500\,000 - 37\,507\,500 = -33\,007\,500 > -6 \times 10^{11}$.

For $r$ slightly above 1, the terms with $k > 300$ (where $900 - 3k < 0$) are amplified by $r^{k-1}$, causing $s(r)$ to decrease monotonically and unboundedly. Thus $s$ crosses $-6 \times 10^{11}$ exactly once. Evaluating at $r = 1.01$ confirms $s(1.01) \ll -6 \times 10^{11}$, establishing that the root lies in $(1, 1.01)$. $\square$

Theorem (Bisection Convergence). The bisection method on $g(r) = s(r) + 6 \times 10^{11}$ over $[1, 1.01]$ converges to 12 decimal places in at most $\lceil \log_2(0.01 / 10^{-13}) \rceil = 40$ iterations.

Proof. Bisection halves the interval at each step. Starting with width $0.01$, after $m$ steps the width is $0.01 / 2^m$. For 12-decimal-place accuracy (error $< 5 \times 10^{-13}$), we need $0.01/2^m < 5 \times 10^{-13}$, i.e., $m > \log_2(2 \times 10^{10}) \approx 34.2$. Taking $m = 40$ suffices with margin. $\square$

Editorial

We else. We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

    n = 5000
    target = -600000000000

        geo = (r^n - 1) / (r - 1)
        dge = (n * r^(n+1) - (n+1) * r^n + 1) / (r - 1)^2
        Return 900 * geo - 3 * dge

    lo = 1.0, hi = 1.01
    For i from 1 to 50:
        mid = (lo + hi) / 2
        If s(mid) > target then
            lo = mid
        else:
            hi = mid
    Return mid // rounded to 12 decimal places

Complexity Analysis

• Time: $O(\log(1/\varepsilon))$ bisection iterations, each requiring $O(1)$ arithmetic with the closed-form (or $O(n)$ if using direct summation). With the closed form, total time is $O(\log(1/\varepsilon))$.
• Space: $O(1)$.

Answer

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

// s(r) = sum_{k=1}^{5000} (900 - 3k) * r^{k-1}
// Using closed form:
// s(r) = 900 * (r^5000 - 1)/(r - 1) - 3 * (5000*r^5001 - 5001*r^5000 + 1) / (r-1)^2

// For numerical stability, use direct summation with long double
// or use the closed form carefully.

long double s_func(long double r) {
    // Direct summation might lose precision for r near 1 with 5000 terms.
    // Use closed form with long double.
    long double r5000 = powl(r, 5000);
    long double r5001 = r5000 * r;
    long double rm1 = r - 1.0L;

    long double geo = (r5000 - 1.0L) / rm1;
    long double ageo = (5000.0L * r5001 - 5001.0L * r5000 + 1.0L) / (rm1 * rm1);

    return 900.0L * geo - 3.0L * ageo;
}

int main() {
    long double target = -600000000000.0L;

    // Bisection on [1.0, 1.01]
    long double lo = 1.0L, hi = 1.01L;

    // Verify signs
    // s(1.0) is about -33007500, so s(1.0) - target > 0
    // s(1.01) should be very negative, so s(1.01) - target < 0

    for (int iter = 0; iter < 200; iter++) {
        long double mid = (lo + hi) / 2.0L;
        long double val = s_func(mid);
        if (val > target) {
            lo = mid;
        } else {
            hi = mid;
        }
    }

    printf("%.12Lf\n", lo);
    return 0;
}

"""
Problem 235: An Arithmetic Geometric Sequence

Find r (to 12 decimal places) such that
s(r) = sum_{k=1}^{5000} (900 - 3k) * r^{k-1} = -600000000000.
"""

from decimal import Decimal, getcontext

def solve():
    getcontext().prec = 50

    def s_func(r):
        """Compute s(r) using closed form with Decimal for precision."""
        r5000 = r ** 5000
        r5001 = r5000 * r
        rm1 = r - 1

        geo = (r5000 - 1) / rm1
        ageo = (5000 * r5001 - 5001 * r5000 + 1) / (rm1 * rm1)
        return 900 * geo - 3 * ageo

    target = Decimal("-600000000000")

    # Bisection
    lo = Decimal("1.0")
    hi = Decimal("1.01")

    for _ in range(200):
        mid = (lo + hi) / 2
        val = s_func(mid)
        if val > target:
            lo = mid
        else:
            hi = mid

    # Format to 12 decimal places
    result = f"{lo:.12f}"
    print(result)

if __name__ == "__main__":
    solve()