Detailed mathematical approach

Problem Summary

For a positive integer \(n\), let \(s(n)\) denote the sum of its proper divisors. A number is called abundant when \(s(n) \gt n\). The task is to add all positive integers that cannot be written as \(a+b\) with both \(a\) and \(b\) abundant.

The crucial reduction is given in the problem statement itself: every integer greater than \(28123\) can be written as the sum of two abundant numbers. Therefore the computation only needs the finite interval \(1 \le n \le L\) with \(L=28123\).

Mathematical Approach

The solution has two mathematical ingredients. First, classify every integer up to \(L\) by its proper-divisor sum. Second, build the set of all sums of two abundant numbers up to the same limit. Once those reachable sums are known, the answer is just the sum of the numbers that were never reached.

Proper-Divisor Sums and the Definition of Abundance

Define the aliquot sum by

$s(n)=\sum_{\substack{d \mid n \\ 1 \le d \lt n}} d.$

Then \(n\) is deficient if \(s(n) \lt n\), perfect if \(s(n)=n\), and abundant if \(s(n) \gt n\). The first abundant number is \(12\), because

$s(12)=1+2+3+4+6=16 \gt 12.$

This already gives one useful observation: no integer below \(24\) can be a sum of two abundant numbers, since the smallest possible such sum is \(12+12\).

Reducing the Problem to a Finite Sumset

Let

$A=\{a\in\{1,2,\dots,L\}: s(a)\gt a\}$

be the set of abundant numbers up to the search limit. We only care whether a value \(n\le L\) belongs to

$E=(A+A)\cap\{1,2,\dots,L\}=\{a_i+a_j:\ a_i,a_j\in A,\ a_i+a_j\le L\}.$

The requested total is therefore

$\sum_{\substack{1 \le n \le L \\ n\notin E}} n.$

That formula is the whole problem in compact form: build \(A\), mark every element of \(E\), and add the integers that remain outside \(E\).

Computing Every \(s(n)\) at Once

The implementations do not factor each number independently. Instead, they use a divisor sieve. For each possible proper divisor \(d\), add \(d\) to every multiple \(2d,3d,4d,\dots\le L\). When this process finishes, the entry at position \(n\) has received exactly the contribution of every proper divisor of \(n\), so it equals \(s(n)\).

The running time of this phase is controlled by the harmonic series:

$\sum_{d=1}^{\lfloor L/2 \rfloor}\left\lfloor \frac{L}{d}\right\rfloor = O(L\log L).$

For \(L=28123\), this preprocessing is small enough that a simple array-based sieve is entirely sufficient.

Why the Pair Scan Can Stop Early

After the sieve, the abundant numbers are collected in increasing order. Suppose we fix one abundant number \(a_i\) and then try partners \(a_j\) with \(j\ge i\). Because the list is sorted, the sums \(a_i+a_j\) grow as \(j\) grows. Therefore, once \(a_i+a_j\gt L\), every later partner also produces a sum above \(L\), so the inner scan can stop immediately.

This monotonicity is the key invariant behind the second phase. It means the algorithm never examines useless pairs beyond the search limit, even though it still conceptually explores the sumset \(A+A\).

Worked Example

Up to \(25\), the abundant numbers are \(12,18,20,24\). The first reachable sum is

$12+12=24.$

The next partner already gives

$12+18=30 \gt 25,$

so there is no reason to test \(12+20\) or \(12+24\) when the limit is \(25\). Thus \(24\) is marked as expressible, while \(25\) is never marked and must be included in the final answer.

How the Code Works

Phase 1: Build the Divisor-Sum Table

The C++, Python, and Java implementations allocate an integer table of length \(L+1\) and fill it by the divisor sieve. A single left-to-right pass over that table then identifies every abundant number from \(12\) to \(L\). Because this pass is increasing, the abundant list is automatically sorted.

Phase 2: Mark Every Reachable Sum

A Boolean table indexed by \(0,1,\dots,L\) records whether a number can be written as the sum of two abundant numbers. The implementations loop over abundant pairs with the second index starting at the first, so each unordered pair is handled once. If the sum stays within the limit, the Boolean entry is marked; if the sum exceeds the limit, the inner loop breaks immediately.

Phase 3: Accumulate the Missing Integers

The final pass simply adds all \(n\) with \(1 \le n \le L\) whose Boolean entry is still false. The implementations also verify two checkpoint cases before using the default bound, confirming that the partial answers for \(L=50\) and \(L=100\) are \(891\) and \(2766\).

Complexity Analysis

The divisor sieve costs \(O(L\log L)\). If \(k=|A|\) is the number of abundant numbers up to \(L\), then the marking phase is \(O(k^2)\) in the worst case, with practical savings from the early break in the sorted list. The final accumulation is \(O(L)\).

Space usage is \(O(L)\): one integer array for proper-divisor sums, one Boolean array for representability, and the list of abundant numbers. For \(L=28123\), these structures are easily small enough for a straightforward implementation in all three languages.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=23
2. Abundant number: Wikipedia - Abundant number
3. Aliquot sum: Wikipedia - Aliquot sum
4. Additional background: MathWorld - Abundant Number