[C/C++] Project Euler #23 - Non-Abundant Sums

Project Euler #23 - Non-Abundant Sums asks the following:

A number is classified as either a “Deficient number,” a “Perfect number,” or an “Abundant number” based on the sum of its proper divisors. If the sum of the proper divisors of a number is less than the number itself, it is classified as deficient. If the sum equals the number, it is called perfect. If the sum is greater than the number, it is classified as abundant. For instance, the proper divisors of 12 are 1, 2, 3, 4, and 6, and their sum is 16, so 12 is an abundant number.

The problem asks you to:
1. Define “non-abundant sums” as all positive integers that cannot be written as the sum of two abundant numbers.  Calculate the sum of all such integers.
2. Assume that all integers greater than 28123 can be expressed as the sum of two abundant numbers.  Within this range, find all numbers that qualify as non-abundant sums and compute their total sum.

 

This problem is not significantly different from other problems that involve finding the sum of divisors.

The sum of divisors is usually denoted as \(\sigma(n)\).  If we exclude the number itself from this sum, the number is classified as deficient if the sum is less than the number, perfect if it is equal, and abundant if it is greater.

Abundant numbers, by definition, can appear infinitely many times. It has been proven that the distribution of abundant numbers neither increases nor decreases significantly as the range of numbers grows.

There are two key cases where abundant numbers arise:
1. Multiples of perfect numbers (excluding the perfect numbers themselves).
2. Multiples of abundant numbers (including the abundant numbers themselves).

To become an abundant number, a number generally needs to be composed of small prime factors.

The smallest abundant number is 12, which happens to be a multiple of the perfect number 6.

Perfect numbers can be expressed as follows:

\[ \sigma(n) = \sum_{d \mid n} d = 2n \]

If we multiply a perfect number n by k > 1, we get:

\[ \sigma(kn) = \sum_{d \mid kn} d > \sum_{d \mid n} kd = k \sigma(n) \]

Thus, the result becomes an abundant number.

For example, 6 has the divisors 1, 2, 3, and 6. The number 6k (where k > 1) will have the divisors k, 2k, 3k, 6k, along with the divisor 1, making it an abundant number. For instance, 12 is 6 \times 2. The divisors of 6, which are 1, 2, 3, and 6, are also divisors of 12, and their multiples (2, 4, 6, 12) are additional divisors. The sum of these multiples is 24, and since 1 and 3 are also divisors of 12, it becomes an abundant number.

The same logic applies when n is already an abundant number, meaning that multiplying an abundant number by k > 1 will still result in an abundant number. This principle can help in identifying abundant numbers more efficiently.

Looking at abundant numbers, the early ones include 12, 18, 24, 30, 36, 42, etc., which are multiples of the perfect number 6. Similarly, numbers like 20, 30, 40, 60, 80, etc., are multiples of the abundant number 20, and 56, 84, etc., are multiples of the perfect number 28.

However, in this problem, simply reducing the method of identifying these numbers will not significantly improve the overall speed.

The main challenge lies in finding numbers that cannot be expressed as the sum of two abundant numbers.

If there were no limit to the numbers that cannot be expressed as the sum of two abundant numbers, it would have been impossible to find all such cases using a computer. Since a limit is provided, the approach involves finding all numbers within this limit that can be expressed as the sum of two abundant numbers and subtracting these from the total set of numbers within the limit. This seems to be the most practical method to solve the problem. (While multiplication can be handled through factorization, addition does not have a similarly straightforward approach due to its numerous possibilities.)

 

abundant numbers

As a result, the source code produced for this problem reflects this approach.

//------------------------------------------------
//    Project Euler #23 - Non-Abundant Sums
//        - by Aubrey Choi
//        - created at 2015-01-26
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

#define    MAX    28123

bool isabundant(int n);

int main()
{
    int abundant[MAX];
    int n = 0;
    unsigned num[MAX/32+1];

    abundant[n++] = 12;

    memset(num, 0, sizeof(num));

    //    get all abundant numbers below 28123.
    for( int i = 14 ; i <= MAX ; i++ )
        if( isabundant(i) ) abundant[n++] = i;
    
    //    check all abundant sums.
    for( int i = 0 ; i < n ; i++ )
    {
        for( int j = 0 ; j < n ; j++ )
        {
            int v = abundant[i]+abundant[j];
            if( v > MAX ) break;
            num[v/32] |= 1<<(v%32);
        }
    }

    int sum = 0, max = 0;
    for( int i = 1 ; i <= MAX ; i++ )
    {
        if( !(num[i/32] & 1<<(i%32)) )
        {
            max = i;
            sum += i;
        }
    }
    printf("Ans = %d(%d)\n", sum, max);
}

bool isabundant(int n)
{
    int t = n;
    int sum = 1;
    while( t%2 == 0 ) { t/=2; sum = sum*2 + 1; }
    for( int i = 3 ; t > 1 ; i+=2 )
    {
        int c = 1;
        while( t%i == 0 ) { t/=i; c = c*i + 1; }
        sum *= c;
    }
    return sum > 2*n;
}