Problem 632: Sum of Divisors of Sum of Divisors

Mathematical Foundation

Theorem 1 (Multiplicativity of $\sigma$). The function $\sigma$ is multiplicative: $\sigma(mn) = \sigma(m)\sigma(n)$ whenever $\gcd(m,n) = 1$.

Proof. If $\gcd(m,n) = 1$, then every divisor $d$ of $mn$ factors uniquely as $d = d_1 d_2$ with $d_1 \mid m$ and $d_2 \mid n$. Therefore

Lemma 1 (Prime Power Formula). For a prime $p$ and integer $k \geq 1$,

Proof. The divisors of $p^k$ are $1, p, p^2, \ldots, p^k$. Their sum is the geometric series $\sum_{i=0}^{k} p^i = (p^{k+1}-1)/(p-1)$. $\square$

Theorem 2 (Divisor Sieve Correctness). The additive sieve that, for each $d = 1, \ldots, N$, adds $d$ to $\sigma(m)$ for every multiple $m = d, 2d, \ldots, \lfloor N/d \rfloor \cdot d$, correctly computes $\sigma(n)$ for all $n \leq N$.

Proof. For a fixed $n \leq N$, the sieve adds $d$ to $\sigma(n)$ exactly when $d \mid n$ and $d \leq N$. Since $n \leq N$, every divisor $d$ of $n$ satisfies $d \leq n \leq N$, so all divisors are counted. Hence $\sigma(n) = \sum_{d \mid n} d$ is computed correctly. $\square$

Theorem 3 (Average Order). $\sum_{n=1}^{N} \sigma(n) = \frac{\pi^2}{12} N^2 + O(N \log N)$.

Proof. $\sum_{n=1}^{N}\sigma(n) = \sum_{d=1}^{N} d \lfloor N/d \rfloor = \sum_{d=1}^{N} d(N/d - \{N/d\}) = N \sum_{d=1}^{N} 1 - \sum_{d=1}^{N} d\{N/d\}$. More precisely, $\sum_{d=1}^{N} d\lfloor N/d\rfloor = N\sum_{d=1}^N 1 + \ldots$. The standard computation via $\sum_{d=1}^{N}\lfloor N/d\rfloor/d$ and the asymptotic $\sum_{d=1}^{N} 1/d^2 \to \pi^2/6$ gives the leading term $\frac{\pi^2}{12}N^2$. $\square$

Lemma 2 (Sieve Range Bound). For $n \leq N$, $\sigma(n) \leq n \cdot H_n \leq N \cdot (1 + \ln N)$, where $H_n$ is the $n$-th harmonic number. Thus the sieve for $\sigma(\sigma(n))$ must extend to $M = O(N \log N)$.

Proof. $\sigma(n)/n = \sum_{d \mid n} 1/d \leq \sum_{d=1}^{n} 1/d = H_n \leq 1 + \ln n$. Therefore $\sigma(n) \leq n(1 + \ln n) \leq N(1 + \ln N)$. $\square$

Editorial

sigma(n) = sum of divisors of n. S(N) = sum_{n=1}^{N} sigma(sigma(n)). Method 1: Sieve for sigma, then lookup Method 2: Trial division (verification). We sieve sigma(n) for n = 1..M where M = max possible sigma(n). Finally, else.

Pseudocode

Sieve sigma(n) for n = 1..M where M = max possible sigma(n)
Compute S(N) = sum of sigma(sigma(n))
else

Complexity Analysis

• Time: $O(M \log M)$ for the sieve where $M = O(N \log N)$, giving $O(N \log N \cdot \log(N \log N)) = O(N \log^2 N)$. The summation is $O(N)$ with table lookups.
• Space: $O(M) = O(N \log N)$ for the sieve array.

Answer

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

/*
 * Problem 632: Sum of Divisors of Sum of Divisors
 *
 * sigma(n) = sum of divisors.
 * Compute S(N) = sum_{n=1}^{N} sigma(sigma(n)).
 *
 * Method 1: Sieve for sigma, then lookup/compute
 * Method 2: Trial division (verification)
 */

const int MAXN = 100001;
ll sig[MAXN];

void sieve_sigma(int N) {
    memset(sig, 0, sizeof(sig));
    for (int d = 1; d <= N; d++)
        for (int m = d; m <= N; m += d)
            sig[m] += d;
}

ll sigma_trial(ll n) {
    ll total = 0;
    for (ll d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            total += d;
            if (d != n / d) total += n / d;
        }
    }
    return total;
}

int main() {
    int N = 100000;
    sieve_sigma(N);

    // Verify
    for (int n = 1; n <= 1000; n++)
        assert(sig[n] == sigma_trial(n));

    // Compute S(N)
    ll S = 0;
    for (int n = 1; n <= N; n++) {
        ll sn = sig[n];
        if (sn <= N) S += sig[sn];
        else S += sigma_trial(sn);
    }

    cout << "S(" << N << ") = " << S << endl;
    return 0;
}

"""
Problem 632: Sum of Divisors of Sum of Divisors

sigma(n) = sum of divisors of n.
S(N) = sum_{n=1}^{N} sigma(sigma(n)).

Method 1: Sieve for sigma, then lookup
Method 2: Trial division (verification)
"""

def sigma_sieve(N):
    """Compute sigma(n) for n=1..N via divisor sieve."""
    sig = [0] * (N + 1)
    for d in range(1, N + 1):
        for m in range(d, N + 1, d):
            sig[m] += d
    return sig

def sigma_trial(n):
    """Compute sigma(n) via trial division."""
    total = 0
    d = 1
    while d * d <= n:
        if n % d == 0:
            total += d
            if d != n // d:
                total += n // d
        d += 1
    return total

# Compute
N = 10000
sig = sigma_sieve(N)

# Verify sieve against trial division
for n in range(1, 1001):
    assert sig[n] == sigma_trial(n), f"n={n}: sieve={sig[n]}, trial={sigma_trial(n)}"

# Compute S(N) = sum sigma(sigma(n))
def compute_S(N, sig):
    total = 0
    for n in range(1, N + 1):
        sn = sig[n]
        if sn <= N:
            total += sig[sn]
        else:
            total += sigma_trial(sn)
    return total

S_small = compute_S(10, sig)
print(f"S(10) = {S_small}")  # Should be sum of sigma(sigma(n)) for n=1..10

# Verify multiplicativity
assert sig[1] == 1
assert sig[2] == 3
assert sig[6] == 12
assert sig[12] == 28
assert sig[28] == 56

print(f"S(100) = {compute_S(100, sig)}")
print(f"S(1000) = {compute_S(1000, sig)}")
print("All verifications passed.")