Project Euler Problem 23

Project Euler Problem 23

Solution

Answer: 4179871

We seek all positive integers that cannot be written as the sum of two abundant numbers.

A number is abundant if the sum of its proper divisors exceeds the number itself.

The problem gives the key bound:

• Every integer greater than $28123$ can be written as the sum of two abundant numbers.

So the task is:

1. Generate all abundant numbers up to $28123$.
2. Mark every number representable as the sum of two abundant numbers.
3. Sum all integers from $1$ to $28123$ that are not marked.

A divisor-sum sieve makes this efficient.

Python code:

LIMIT = 28123

# Sum of proper divisors for each number
div_sum = [0] * (LIMIT + 1)

for i in range(1, LIMIT // 2 + 1):
    for j in range(i * 2, LIMIT + 1, i):
        div_sum[j] += i

# Collect abundant numbers
abundant = [n for n in range(1, LIMIT + 1) if div_sum[n] > n]

# Mark numbers expressible as sum of two abundant numbers
can_be_written = [False] * (LIMIT + 1)

for i in range(len(abundant)):
    for j in range(i, len(abundant)):
        s = abundant[i] + abundant[j]
        if s <= LIMIT:
            can_be_written[s] = True
        else:
            break

# Sum numbers that cannot be expressed this way
answer = sum(n for n in range(1, LIMIT + 1) if not can_be_written[n])

print(answer)

Tracing the logic:

• $12$ is the first abundant number.
• $24 = 12 + 12$ is the first expressible sum.
• The sieve correctly computes divisor sums.
• The nested loops enumerate all abundant-pair sums up to the limit.
• The final accumulation matches the known Project Euler result.

Answer: 4179871