All challenges
Hard 0 solved 0% acceptance

Non-Abundant Sums

Add up the numbers up to a limit that cannot be written as the sum of two abundant numbers.

What you'll learn

  • Compute divisor sums for a range with a sieve
  • Mark reachable sums with a boolean array
  • Cut a double loop short once sums pass the limit

Problem

A number is abundant when its proper divisors (all divisors except itself) add up to more than it. 12 is the smallest: 1 + 2 + 3 + 4 + 6 = 16. Some numbers can be written as the sum of two abundant numbers (the same one may be used twice, as in 24 = 12 + 12) and some cannot. Add up every positive integer from 1 to limit that cannot.

Implement non_abundant_sums(limit).

Find the divisor sums for every number at once with a sieve, list the abundant numbers, then mark every pair sum that stays within the limit.

Input

limit: The largest number to check.

Output

Return the sum of all n with 1 ≤ n ≤ limit that are not the sum of two abundant numbers.

Constraints

1 ≤ limit ≤ 10,000

Examples

Example 1
Input:
limit = 23

Expected output:
expected = 276
Input:
long long limit = 23;

Expected output:
long long expected = 276;
Input:
long limit = 23;

Expected output:
long expected = 276;

Explanation

No two abundant numbers add up to 23 or less, so every number counts: 1 + 2 + ... + 23 = 276.

Example 2
Input:
limit = 30

Expected output:
expected = 411
Input:
long long limit = 30;

Expected output:
long long expected = 411;
Input:
long limit = 30;

Expected output:
long expected = 411;

Explanation

24 = 12 + 12 and 30 = 12 + 18 are left out, so the answer is 465 − 24 − 30 = 411.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

For each i, add i to the divisor sum of 2i, 3i, 4i, ...

Hint 2

Collect the abundant numbers in increasing order.

Hint 3

For each pair a ≤ b, stop the inner loop once a + b passes the limit.

Expected complexity

O(limit log limit + A²) time for A abundant numbers, O(limit) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.