Project Euler

Geometric Series Truncation

Let S(r, n) = sum_(k=0)^n r^k for integer r >= 2. Find sum_(r=2)^100 S(r, r) mod (10^9+7).

Source sync Apr 19, 2026

Problem #0911

Level Level 36

Solved By 196

Languages C++, Python

Answer 5679.934966

Length 221 words

modular_arithmeticnumber_theoryalgebra

An irrational number $x$ can be uniquely expressed as a continued fraction $[a_0; a_1,a_2,a_3,\dots]$: $$ x=a_{0}+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ddots}}} $$ where $a_0$ is an integer and $a_1,a_2,a_3,\dots$ are positive integers.

Define $k_j(x)$ to be the geometric mean of $a_1,a_2,\dots,a_j$.

That is, $k_j(x)=(a_1a_2 \cdots a_j)^{1/j}$.

Also define $k_\infty(x)=\lim_{j\to \infty} k_j(x)$.

Khinchin proved that almost all irrational numbers $x$ have the same value of $k_\infty(x)\approx2.685452\dots$ known as Khinchin's constant. However, there are some exceptions to this rule.

For $n\geq 0$ define $$\rho_n = \sum_{i=0}^{\infty} \frac{2^n}{2^{2^i}} $$ For example $\rho_2$, with continued fraction beginning $[3; 3, 1, 3, 4, 3, 1, 3,\dots]$, has $k_\infty(\rho_2)\approx2.059767$.

Find the geometric mean of $k_{\infty}(\rho_n)$ for $0\leq n\leq 50$, giving your answer rounded to six digits after the decimal point.

Problem 911: Geometric Series Truncation

Mathematical Foundation

Theorem 1 (Geometric Series). For $r \ne 1$ and non-negative integer $n$ ,

S(r, n) = \sum_{k=0}^{n} r^k = \frac{r^{n+1} - 1}{r - 1}.

Proof. Let $S = \sum_{k=0}^{n} r^k$ . Then

rS = \sum_{k=0}^{n} r^{k+1} = \sum_{k=1}^{n+1} r^k.

Subtracting the original sum:

rS - S = r^{n+1} - r^0 = r^{n+1} - 1.

Since $r \ne 1$ , we divide both sides by $(r - 1)$ to obtain $S = (r^{n+1} - 1)/(r - 1)$ . $\square$

Theorem 2 (Fermat’s Little Theorem). For a prime $p$ and integer $a$ with $\gcd(a, p) = 1$ ,

a^{p-1} \equiv 1 \pmod{p},

and consequently $a^{-1} \equiv a^{p-2} \pmod{p}$ .

Proof. Consider the map $\phi_a : (\mathbb{Z}/p\mathbb{Z})^* \to (\mathbb{Z}/p\mathbb{Z})^*$ defined by $\phi_a(x) = ax$ . Since $\gcd(a, p) = 1$ , this map is injective on the finite set $\{1, 2, \ldots, p-1\}$ , hence bijective. Therefore

\prod_{x=1}^{p-1} (ax) = \prod_{x=1}^{p-1} x,

which gives $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$ . Since $\gcd((p-1)!, p) = 1$ , we cancel to obtain $a^{p-1} \equiv 1 \pmod{p}$ . Multiplying both sides by $a^{-1}$ yields $a^{p-2} \equiv a^{-1} \pmod{p}$ . $\square$

Lemma 1. For $2 \le r \le 100$ and $p = 10^9 + 7$ , the modular inverse $(r-1)^{-1} \bmod p$ exists.

Proof. We have $1 \le r - 1 \le 99 < p$ , so $r - 1 \not\equiv 0 \pmod{p}$ . Since $p$ is prime, $\gcd(r-1, p) = 1$ , and the inverse exists by Theorem 2. $\square$

Theorem 3 (Correctness). The value $\sum_{r=2}^{100} S(r, r) \bmod p$ equals $\sum_{r=2}^{100} \bigl[(r^{r+1} - 1) \cdot (r-1)^{p-2}\bigr] \bmod p$ .

Proof. By Theorem 1, $S(r, r) = (r^{r+1} - 1)/(r - 1)$ over $\mathbb{Z}$ . By Lemma 1, $(r-1)^{-1}$ exists modulo $p$ , and by Theorem 2, $(r-1)^{-1} \equiv (r-1)^{p-2} \pmod{p}$ . The natural ring homomorphism $\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$ preserves addition and multiplication, so

S(r, r) \bmod p \equiv (r^{r+1} - 1) \cdot (r-1)^{p-2} \pmod{p}.

Summing over $r = 2, \ldots, 100$ and reducing modulo $p$ gives the result. $\square$

Editorial

S(r, n) = sum_{k=0}^{n} r^k = (r^{n+1} - 1) / (r - 1). Find sum_{r=2}^{100} S(r, r) mod 10^9+7. 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

    p = 10^9 + 7
    total = 0
    For r from 2 to 100:
        numerator = (pow_mod(r, r+1, p) - 1 + p) mod p
        denominator_inv = pow_mod(r - 1, p - 2, p)
        total = (total + numerator * denominator_inv) mod p
    Return total

    result = 1
    base = base mod mod
    While exp > 0:
        if exp is odd:
            result = (result * base) mod mod
        exp = exp >> 1
        base = (base * base) mod mod
    Return result

Complexity Analysis

Time: $O(R \log p)$ where $R = 99$ . Each of the 99 terms requires two modular exponentiations: $r^{r+1} \bmod p$ in $O(\log r)$ and $(r-1)^{p-2} \bmod p$ in $O(\log p)$ . The dominant cost is $O(R \log p) \approx 99 \times 30 \approx 2970$ modular multiplications.
Space: $O(1)$ . Only a constant number of variables are maintained.

Answer

\boxed{5679.934966}

C++ project_euler/problem_911/solution.cpp

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

/*
 * Problem 911: Geometric Series Truncation
 *
 * S(r, n) = sum_{k=0}^{n} r^k = (r^{n+1} - 1) / (r - 1)
 * Find sum_{r=2}^{100} S(r, r) mod 10^9+7.
 *
 * Two methods:
 *   1. Closed-form: S(r,r) = (r^{r+1} - 1) * (r-1)^{-1} mod p
 *   2. Direct summation: iterate powers 1, r, r^2, ..., r^r
 *
 * Modular inverse via Fermat: (r-1)^{p-2} mod p.
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

/* Method 1: Closed-form with Fermat inverse */
long long solve_closed() {
    long long total = 0;
    for (int r = 2; r <= 100; r++) {
        long long num = (power(r, r + 1, MOD) - 1 + MOD) % MOD;
        long long inv = power(r - 1, MOD - 2, MOD);
        total = (total + num % MOD * inv % MOD) % MOD;
    }
    return total;
}

/* Method 2: Direct summation */
long long solve_direct() {
    long long total = 0;
    for (int r = 2; r <= 100; r++) {
        long long s = 0, rk = 1;
        for (int k = 0; k <= r; k++) {
            s = (s + rk) % MOD;
            rk = rk * r % MOD;
        }
        total = (total + s) % MOD;
    }
    return total;
}

int main() {
    long long ans1 = solve_closed();
    long long ans2 = solve_direct();

    assert(ans1 == ans2);

    // Verify small exact values
    // S(2,2) = 7, S(3,3) = 40, S(4,4) = 341
    assert((power(2, 3, MOD) - 1 + MOD) % MOD * power(1, MOD - 2, MOD) % MOD == 7);
    assert((power(3, 4, MOD) - 1 + MOD) % MOD * power(2, MOD - 2, MOD) % MOD == 40);

    cout << ans1 << endl;
    return 0;
}

Python project_euler/problem_911/solution.py

"""
Problem 911: Geometric Series Truncation

S(r, n) = sum_{k=0}^{n} r^k = (r^{n+1} - 1) / (r - 1).
Find sum_{r=2}^{100} S(r, r) mod 10^9+7.

Methods:
    1. Closed-form with modular inverse (Fermat)
    2. Direct polynomial evaluation (verification)
    3. Exact computation for small r (cross-check)
"""

from math import log10

MOD = 10**9 + 7

def solve_closed_form(mod: int):
    """Sum S(r, r) for r = 2..100, where S(r,r) = (r^{r+1}-1)/(r-1) mod p."""
    total = 0
    for r in range(2, 101):
        num = (pow(r, r + 1, mod) - 1) % mod
        inv = pow(r - 1, mod - 2, mod)
        total = (total + num * inv) % mod
    return total

def solve_direct(mod: int):
    """Compute each S(r,r) = 1 + r + r^2 + ... + r^r directly."""
    total = 0
    for r in range(2, 101):
        s = 0
        rk = 1  # r^k mod p
        for k in range(r + 1):
            s = (s + rk) % mod
            rk = rk * r % mod
        total = (total + s) % mod
    return total

def s_exact(r: int):
    """Compute S(r, r) = (r^{r+1} - 1) / (r - 1) exactly."""
    return (r ** (r + 1) - 1) // (r - 1)

# Solve
ans_closed = solve_closed_form(MOD)
ans_direct = solve_direct(MOD)

assert ans_closed == ans_direct, f"Mismatch: {ans_closed} vs {ans_direct}"

# Verify exact values for small r
assert s_exact(2) == 7      # 1 + 2 + 4
assert s_exact(3) == 40     # 1 + 3 + 9 + 27
assert s_exact(4) == 341    # 1 + 4 + 16 + 64 + 256
assert s_exact(5) == 3906
assert s_exact(10) == 11111111111

# Verify modular consistency
for r in range(2, 20):
    exact_mod = s_exact(r) % MOD
    num = (pow(r, r + 1, MOD) - 1) % MOD
    inv = pow(r - 1, MOD - 2, MOD)
    closed_mod = num * inv % MOD
    assert exact_mod == closed_mod, f"r={r}: exact={exact_mod}, closed={closed_mod}"

print(ans_closed)