Problem 921: Divisor Chain Lengths

Mathematical Foundation

Theorem 1 (Maximum Divisor Chain Length). For every positive integer $n$, $L(n) = \Omega(n)$, where $\Omega(n) = \sum_{p^k \| n} k$ denotes the number of prime factors of $n$ counted with multiplicity.

Proof. We establish matching upper and lower bounds.

Upper bound. Let $n = a_1 > a_2 > \cdots > a_k = 1$ be any divisor chain. At each step, $a_{i+1} \mid a_i$ and $a_{i+1} < a_i$, so $a_i / a_{i+1} \geq 2$. Hence the quotient $a_i / a_{i+1}$ contributes at least one prime factor (with multiplicity), giving $\Omega(a_i) \geq \Omega(a_{i+1}) + 1$. Summing telescopically:

Lower bound. Write $n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$. Construct the chain by removing one prime factor at a time:

This chain has exactly $e_1 + e_2 + \cdots + e_r = \Omega(n)$ steps. $\square$

Theorem 2 (Summation Formula). For all $N \geq 1$:

Proof. By definition, $\Omega(n) = \sum_{\substack{p^k \mid n \\ p \text{ prime},\, k \geq 1}} 1$. Exchanging the order of summation:

Lemma 1 (Asymptotic Behavior). $\displaystyle\sum_{n=1}^{N} \Omega(n) = N \ln \ln N + M_1 N + O\!\left(\frac{N}{\ln N}\right)$, where $M_1 = \gamma + \sum_{p}\left(\ln\frac{p}{p-1} - \frac{1}{p}\right)$ and $\gamma$ is the Euler—Mascheroni constant.

Proof. From Theorem 2:

By Mertens’ second theorem, $\sum_{p \leq N} \frac{1}{p} = \ln\ln N + M + O(1/\ln N)$ where $M$ is the Meissel—Mertens constant. The result follows. $\square$

Editorial

Alternative direct formula (no sieve needed). We sieve approach: compute Omega(n) for all n <= N. We then p is prime; mark composites. Finally, iterate over each prime power p^k, add 1 to all multiples.

Pseudocode

Sieve approach: compute Omega(n) for all n <= N
p is prime; mark composites
For each prime power p^k, add 1 to all multiples
Use Theorem 2 directly

Complexity Analysis

• Time: $O(N \log \log N)$ for both the sieve-based and direct approaches. The sieve of Eratosthenes runs in $O(N \log \log N)$. The inner loop over prime powers contributes $\sum_{p} \sum_{k} N/p^k = O(N \log \log N)$.
• Space: $O(N)$ for the sieve array. The direct formula method requires $O(N / \ln N)$ space for the prime list, or $O(N)$ for a bit sieve.

Answer

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

/*
 * Problem 921: Divisor Chain Lengths
 *
 * L(n) = max divisor chain length from n to 1 = Omega(n).
 * Find sum_{n=1}^{10^5} Omega(n) mod 10^9+7.
 *
 * Key insight: The longest chain from n to 1 via proper divisors
 * has length Omega(n) = sum of exponents in prime factorization.
 *
 * Proof:
 *   Upper bound: each step a_{i+1} | a_i, a_{i+1} < a_i implies
 *     a_i/a_{i+1} >= 2, so Omega decreases by >= 1 per step.
 *   Lower bound: divide by one prime at a time.
 *
 * Sieve approach: for each prime p, for each power p^k <= N,
 * add 1 to Omega(m) for all multiples m of p^k.
 *
 * Alternative formula: sum Omega(n) = sum_{p prime} sum_k floor(N/p^k).
 *
 * Complexity: O(N log log N) sieve, O(N) summation.
 */

int main() {
    const int N = 100000;
    const long long MOD = 1000000007;

    vector<int> omega(N + 1, 0);
    for (int p = 2; p <= N; p++) {
        if (omega[p] == 0) { // p is prime
            for (long long pk = p; pk <= N; pk *= p) {
                for (long long m = pk; m <= N; m += pk) {
                    omega[m]++;
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += omega[i];
    }

    cout << ans % MOD << endl;

    // Verification
    assert(omega[1] == 0);
    assert(omega[6] == 2);   // 2 * 3
    assert(omega[8] == 3);   // 2^3
    assert(omega[12] == 3);  // 2^2 * 3
    assert(omega[60] == 4);  // 2^2 * 3 * 5
    assert(omega[64] == 6);  // 2^6

    return 0;
}

"""
Problem 921: Divisor Chain Lengths

L(n) = maximum divisor chain length from n to 1 = Omega(n).
Find sum of L(n) for n = 1..10^5, mod 10^9+7.

Key ideas:
    - L(n) = Omega(n), the number of prime factors with multiplicity.
    - Each chain step divides by one prime; this is optimal.
    - Compute Omega(n) via sieve of prime powers.
    - Summation formula: sum Omega(n) = sum_{p prime} sum_k floor(N/p^k).

Methods:
    1. Sieve-based Omega computation
    2. Direct summation formula over primes
    3. Verification via factorization
"""

from collections import Counter

MOD = 10**9 + 7

def sieve_omega(N: int) -> list:
    """Compute Omega(n) for n = 0..N using a sieve."""
    omega = [0] * (N + 1)
    for p in range(2, N + 1):
        if omega[p] == 0:  # p is prime
            pk = p
            while pk <= N:
                for m in range(pk, N + 1, pk):
                    omega[m] += 1
                pk *= p
    return omega

def sum_omega_formula(N: int) -> int:
    """Compute sum_{n=1}^{N} Omega(n) = sum_{p prime} sum_k floor(N/p^k)."""
    # Sieve primes up to N
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(N**0.5) + 1):
        if is_prime[p]:
            for m in range(p*p, N + 1, p):
                is_prime[m] = False

    total = 0
    for p in range(2, N + 1):
        if is_prime[p]:
            pk = p
            while pk <= N:
                total += N // pk
                pk *= p
    return total

def omega_brute(n: int) -> int:
    """Compute Omega(n) by trial division."""
    count = 0
    d = 2
    while d * d <= n:
        while n % d == 0:
            count += 1
            n //= d
        d += 1
    if n > 1:
        count += 1
    return count

# Solve
N = 10**5
omega = sieve_omega(N)
answer = sum(omega[1:N+1]) % MOD

# Verify methods agree
assert sum(omega[1:N+1]) == sum_omega_formula(N)

# Verify Omega for small values
assert omega[1] == 0
assert omega[6] == 2   # 2 * 3
assert omega[8] == 3   # 2^3
assert omega[12] == 3  # 2^2 * 3
assert omega[60] == 4  # 2^2 * 3 * 5

# Verify against brute force for small n
for n in range(1, 1000):
    assert omega[n] == omega_brute(n), f"n={n}: sieve={omega[n]}, brute={omega_brute(n)}"

print(answer)