Project Euler

Abundant Number Chains

Define s(n) = sigma(n) - n (sum of proper divisors). An abundant chain of length k starting at n is a sequence n, s(n), s(s(n)),... where each term is abundant (s(term) > term) for k consecutive st...

Source sync Apr 19, 2026

Problem #0966

Level Level 38

Solved By 145

Languages C++, Python

Answer 29337152.09

Length 325 words

number_theorysequencebrute_force

Let $I(a, b, c)$ be the largest possible area of intersection between a triangle of side lengths $a, b, c$ and a circle which has the same area as the triangle.

For example $I(3, 4, 5) \approx 4.593049$ and $I(3, 4, 6) \approx 3.552564$.

Find the sum of $I(a, b, c)$ for integers $a, b, c$ such that $1 \le a \le b \le c \lt a + b$ and $a + b + c \le 200$.

Give your answer rounded to two digits after the decimal point.

Problem 966: Abundant Number Chains

Mathematical Analysis

Abundant Numbers

Definition. A positive integer $n$ is abundant if $s(n) = \sigma(n) - n > n$ , equivalently $\sigma(n) > 2n$ .

Theorem (Density of Abundant Numbers). The proportion of abundant numbers up to $N$ approaches a constant $\approx 0.2477$ as $N \to \infty$ . The first abundant number is 12, with $s(12) = 1 + 2 + 3 + 4 + 6 = 16 > 12$ .

Aliquot Sequences and Chains

The iteration $n \to s(n) \to s(s(n)) \to \cdots$ defines an aliquot sequence. An abundant chain requires each successive term to also be abundant.

Theorem (Catalan—Dickson Conjecture). Every aliquot sequence either terminates at 0 (if reaching 1), enters a cycle (perfect numbers or sociable numbers), or diverges to infinity. The conjecture that no sequence diverges remains open.

For our problem, we only need to track 5 steps and check abundance at each.

Divisor Sum Sieve

Theorem. $\sigma(n)$ can be computed for all $n \le M$ in $O(M \log M)$ time using a divisor sieve: for each $d$ from 1 to $M$ , add $d$ to $\sigma(kd)$ for $k = 1, 2, \ldots$

Concrete Examples

$n$	$s(n)$	$s^2(n)$	$s^3(n)$	$s^4(n)$	$s^5(n)$	Chain length
12	16	15	9	4	3	1 (s(12)=16>12 but s(16)=15<16)
240	504	1016	…	…	…	>= 5

Derivation

Editorial

s(n) = sigma(n) - n (sum of proper divisors). A number n is abundant if s(n) > n. An “abundant chain” of length L starting at n means: n, s(n), s(s(n)), …, each strictly increasing for L steps. Count n <= 10^5 that start an abundant chain of length >= 5. We sieve** $s(n) = \sigma(n) - n$ for all $n$ up to $M$ (large enough to cover chain elements; $M \approx 10^7$ suffices). We then iterate over each $n \le 10^5$ . Finally, check $s(a_i) > a_i$ (abundance) for $i = 0, 1, 2, 3, 4$ .

Pseudocode

Sieve** $s(n) = \sigma(n) - n$ for all $n$ up to $M$ (large enough to cover chain elements; $M \approx 10^7$ suffices)
For each $n \le 10^5$:
Follow chain: $a_0 = n, a_{i+1} = s(a_i)$
Check $s(a_i) > a_i$ (abundance) for $i = 0, 1, 2, 3, 4$
If all 5 checks pass, count $n$

Proof of Correctness

The divisor sieve correctly computes $\sigma(n)$ . The chain-following checks abundance at each step. If $s(a_i)$ exceeds our sieve range, the chain stops (conservatively).

Complexity Analysis

$O(M \log M)$ for sieve, $O(N \cdot k)$ for chain following.

Answer

\boxed{29337152.09}

C++ project_euler/problem_966/solution.cpp

/*
 * Problem 966: Abundant Number Chains
 * Count n <= 10^5 starting abundant chain of length >= 5.
 */
#include <bits/stdc++.h>
using namespace std;
int main() {
    const int N = 100000;
    const int M = 10000000;
    vector<long long> s(M + 1, 0);
    for (int d = 1; d <= M; d++)
        for (int m = 2*d; m <= M; m += d)
            s[m] += d;
    int count = 0;
    for (int n = 1; n <= N; n++) {
        long long cur = n;
        bool good = true;
        for (int step = 0; step < 5; step++) {
            if (cur > M || cur <= 0) { good = false; break; }
            long long nxt = s[(int)cur];
            if (nxt <= cur) { good = false; break; }
            cur = nxt;
        }
        if (good) count++;
    }
    cout << count << endl;
    return 0;
}

Python project_euler/problem_966/solution.py

"""
Problem 966: Abundant Number Chains

s(n) = sigma(n) - n (sum of proper divisors).
A number n is abundant if s(n) > n.
An "abundant chain" of length L starting at n means:
    n, s(n), s(s(n)), ..., each strictly increasing for L steps.

Count n <= 10^5 that start an abundant chain of length >= 5.

Key results:
    - s(n) computed via divisor sieve
    - Chain requires s(n) > n at every step for 5 consecutive iterations
    - Most chains terminate quickly; long chains are relatively rare

Methods:
    1. sieve_sum_of_proper_divisors — sieve s(n) up to limit
    2. chain_length                — compute chain length from starting n
    3. count_chains                — count all n <= N with chain length >= target
    4. chain_length_distribution   — distribution of chain lengths
"""

def sieve_sum_of_proper_divisors(limit):
    """Compute s(n) = sum of proper divisors for all n up to limit."""
    s = [0] * (limit + 1)
    for d in range(1, limit + 1):
        for multiple in range(2 * d, limit + 1, d):
            s[multiple] += d
    return s

def chain_length(n, s, max_val):
    """Return length of strictly increasing chain starting at n."""
    cur = n
    length = 0
    while cur <= max_val and cur > 0:
        nxt = s[cur]
        if nxt <= cur:
            break
        length += 1
        cur = nxt
    return length

def count_chains(N, target_len, sieve_limit):
    """Count n in [1, N] with chain length >= target_len."""
    s = sieve_sum_of_proper_divisors(sieve_limit)
    count = 0
    examples = []
    lengths = []
    for n in range(1, N + 1):
        cl = chain_length(n, s, sieve_limit)
        lengths.append(cl)
        if cl >= target_len:
            count += 1
            if len(examples) < 10:
                examples.append(n)
    return count, examples, lengths, s

def get_chain(n, s, max_val, max_steps=20):
    """Return the full chain values."""
    chain = [n]
    cur = n
    for _ in range(max_steps):
        if cur > max_val or cur <= 0:
            break
        nxt = s[cur]
        if nxt <= cur:
            break
        chain.append(nxt)
        cur = nxt
    return chain

# Verification with small known facts
s_small = sieve_sum_of_proper_divisors(100)
# s(12) = 1+2+3+4+6 = 16 > 12, so 12 is abundant
assert s_small[12] == 16
# s(6) = 1+2+3 = 6, perfect number
assert s_small[6] == 6
# s(28) = 1+2+4+7+14 = 28, perfect number
assert s_small[28] == 28
# s(1) = 0
assert s_small[1] == 0

# Compute answer
N = 10 ** 5
SIEVE_LIMIT = 10 ** 7
answer, examples, lengths, s = count_chains(N, 5, SIEVE_LIMIT)
print(answer)