Problem 900: Sum of Remainders

Mathematical Analysis

Theorem 1 (Remainder-to-Floor Reduction)

Proof. By definition, $n \bmod k = n - k\lfloor n/k \rfloor$. Summing over $k = 1, \ldots, n$:

Theorem 2 (Floor Function Block Structure)

The function $q \mapsto \lfloor n/q \rfloor$ takes at most $2\lfloor\sqrt{n}\rfloor$ distinct values. For each distinct value $v = \lfloor n/k \rfloor$, the set of $k$ achieving this value forms a contiguous block $[k_{\min}, k_{\max}]$ where:

Proof. For $v \geq 1$, $\lfloor n/k \rfloor = v$ iff $v \leq n/k < v+1$, i.e., $n/(v+1) < k \leq n/v$. The number of distinct values is bounded because either $v \leq \sqrt{n}$ (at most $\sqrt{n}$ choices) or $k \leq \sqrt{n}$ (at most $\sqrt{n}$ choices), giving $\leq 2\sqrt{n}$ blocks total. $\square$

Lemma (Triangular Sum over a Block)

For a contiguous block $[a, b]$ with constant $\lfloor n/k \rfloor = v$:

Derivation: The Dirichlet Hyperbola Method

We compute $T(n) = \sum_{k=1}^{n} k\lfloor n/k \rfloor$ by iterating over distinct values of $\lfloor n/k \rfloor$.

Algorithm:

1. Set $T = 0$, $k = 1$.
2. While $k \leq n$:
   • Let $v = \lfloor n/k \rfloor$.
   • Let $k' = \lfloor n/v \rfloor$ (the last index in this block).
   • Add $v \cdot (k' - k + 1)(k + k') / 2$ to $T$.
   • Set $k = k' + 1$.
3. Return $S(n) = n^2 - T$.

This runs in $O(\sqrt{n})$ iterations.

Concrete Numerical Examples

Example 1: $S(10)$

$S(10) = 0+0+1+2+0+4+3+2+1+0 = 13$

Verification via formula: $T(10) = 1 \cdot 10 + 2 \cdot 5 + 3 \cdot 3 + 4 \cdot 2 + 5 \cdot 2 + 6 \cdot 1 + 7 \cdot 1 + 8 \cdot 1 + 9 \cdot 1 + 10 \cdot 1 = 10 + 10 + 9 + 8 + 10 + 6 + 7 + 8 + 9 + 10 = 87$.

$S(10) = 100 - 87 = 13$. Confirmed.

Example 2: $S(100)$

Using the $O(\sqrt{n})$ algorithm with $\lfloor\sqrt{100}\rfloor = 10$ blocks:

• Block $v=100$: $k=1$, contributes $1 \cdot 100 = 100$
• Block $v=50$: $k=2$, contributes $2 \cdot 50 = 100$
• Block $v=1$: $k=51..100$, contributes $1 \cdot \frac{50 \cdot 151}{2} = 3775$

$S(100) = 10000 - T(100)$. Direct computation yields $S(100) = 4049$.

Verification Table

Alternative Approach: Connection to Divisor Sum

Note that $\sum_{k=1}^{n} \lfloor n/k \rfloor = \sum_{k=1}^{n} d(k)$ is a classical identity (where the left side counts lattice points under the hyperbola $xy = n$). Our sum has an extra factor of $k$, connecting it to the sum-of-divisors function:

where $\sigma(m) = \sum_{d \mid m} d$. This follows from writing $\lfloor n/k \rfloor = \#\{m : k \mid m, 1 \leq m \leq n\}$ and swapping summation order.

Asymptotic Analysis

Using the known asymptotic $\sum_{m=1}^{n} \sigma(m) = \frac{\pi^2}{12} n^2 + O(n \log n)$:

Complexity Analysis

The hyperbola method enables computation for $n$ up to $10^{18}$ in milliseconds.

Answer

/*
 * Problem 900: Sum of Remainders
 *
 * Compute S(n) = sum_{k=1}^{n} (n mod k)
 *            = n^2 - sum_{k=1}^{n} k * floor(n/k)
 *
 * Uses the Dirichlet hyperbola method: floor(n/k) takes O(sqrt(n)) distinct
 * values, so we iterate over blocks of constant floor value.
 *
 * Complexity: O(sqrt(n)) time, O(1) space.
 */

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

typedef long long ll;
typedef __int128 lll;

// Brute force O(n) -- for verification
ll S_brute(ll n) {
    ll s = 0;
    for (ll k = 1; k <= n; k++)
        s += n % k;
    return s;
}

// O(sqrt(n)) via floor-block decomposition
ll S_hyperbola(ll n) {
    ll T = 0;
    ll k = 1;
    while (k <= n) {
        ll v = n / k;
        ll kp = n / v;  // last index in this block
        // Sum of k + (k+1) + ... + kp = (kp - k + 1) * (k + kp) / 2
        ll block_len = kp - k + 1;
        ll block_sum = block_len * (k + kp) / 2;
        T += v * block_sum;
        k = kp + 1;
    }
    return n * n - T;
}

// O(sqrt(n)) with 128-bit arithmetic for very large n
lll S_hyperbola_128(lll n) {
    lll T = 0;
    lll k = 1;
    while (k <= n) {
        lll v = n / k;
        lll kp = n / v;
        lll block_len = kp - k + 1;
        lll block_sum = block_len * (k + kp) / 2;
        T += v * block_sum;
        k = kp + 1;
    }
    return n * n - T;
}

void print_128(lll x) {
    if (x == 0) { cout << "0"; return; }
    if (x < 0) { cout << "-"; x = -x; }
    string s;
    while (x > 0) { s += char('0' + (int)(x % 10)); x /= 10; }
    reverse(s.begin(), s.end());
    cout << s;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Verification against brute force
    cout << "=== Verification ===" << endl;
    cout << setw(8) << "n" << setw(12) << "Brute" << setw(12) << "Hyperbola"
         << setw(8) << "Match" << endl;
    for (ll n : {1LL, 2LL, 5LL, 10LL, 20LL, 50LL, 100LL, 500LL, 1000LL}) {
        ll sb = S_brute(n);
        ll sh = S_hyperbola(n);
        cout << setw(8) << n << setw(12) << sb << setw(12) << sh
             << setw(8) << (sb == sh ? "OK" : "FAIL") << endl;
        assert(sb == sh);
    }

    // Large values
    cout << "\n=== Large computations ===" << endl;
    for (ll n : {1000000LL, 10000000LL, 100000000LL, 1000000000LL}) {
        ll val = S_hyperbola(n);
        double ratio = (double)val / ((double)n * n);
        cout << "S(" << n << ") = " << val
             << ", S/n^2 = " << fixed << setprecision(6) << ratio << endl;
    }

    cout << "\nTheoretical limit: 1 - pi^2/12 = "
         << fixed << setprecision(6) << 1.0 - M_PI * M_PI / 12.0 << endl;

    // Final answer
    ll ans = S_hyperbola(100000000LL);
    cout << "\nAnswer: S(10^8) = " << ans << endl;

    return 0;
}

"""
Problem 900: Sum of Remainders
Compute S(n) = sum_{k=1}^{n} (n mod k) using the Dirichlet hyperbola method.

Key identity: S(n) = n^2 - sum_{k=1}^{n} k * floor(n/k)
The floor function takes O(sqrt(n)) distinct values, enabling block summation.
"""

import math

def S_brute(n):
    """Brute force: O(n) computation of sum of remainders."""
    return sum(n % k for k in range(1, n + 1))

def S_hyperbola(n):
    """
    O(sqrt(n)) computation via floor-block decomposition.
    Groups k by the value v = floor(n/k) and sums k*v over each block.
    """
    T = 0
    k = 1
    while k <= n:
        v = n // k
        kp = n // v  # last k in this block
        # sum of k, k+1, ..., kp = (kp - k + 1)*(k + kp) // 2
        block_sum = (kp - k + 1) * (k + kp) // 2
        T += v * block_sum
        k = kp + 1
    return n * n - T

def S_divisor_sum(n):
    """
    Alternative via sigma function: T(n) = sum_{m=1}^{n} sigma(m).
    O(n sqrt(n)) -- for verification only.
    """
    T = 0
    for m in range(1, n + 1):
        for d in range(1, int(math.isqrt(m)) + 1):
            if m % d == 0:
                T += d
                if d != m // d:
                    T += m // d
    return n * n - T

# --- Verification ---
print("=== Verification: S(n) by three methods ===")
print(f"{'n':>6} {'Brute':>10} {'Hyperbola':>10} {'DivSum':>10} {'Match':>6}")
for n in [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000]:
    sb = S_brute(n)
    sh = S_hyperbola(n)
    sd = S_divisor_sum(n)
    match = "OK" if sb == sh == sd else "FAIL"
    print(f"{n:>6} {sb:>10} {sh:>10} {sd:>10} {match:>6}")
    assert sb == sh == sd, f"Mismatch at n={n}: {sb}, {sh}, {sd}"

# Large computation
for n in [10**6, 10**7, 10**8]:
    val = S_hyperbola(n)
    ratio = val / (n * n)
    print(f"S({n:.0e}) = {val}, ratio S/n^2 = {ratio:.6f}")

print(f"\nTheoretical limit: 1 - pi^2/12 = {1 - math.pi**2/12:.6f}")

answer = S_hyperbola(10**8)
print(f"\nAnswer: S(10^8) = {answer}")

# --- 4-Panel Visualization ---