23. 프로젝트 오일러 #23 : 초과수의 합으로 표현 안되는 자연수들의 합

이번 문제는 약수들의 합을 구하는 기존 문제들과 크게 다를 바가 없습니다.

약수들의 합을 보통은 σ(n)으로 표현을 하는데요.  이 중, 자기자신을 뺀 약수들의 합을 가지고, 자기자신과 적으면 부족수, 같으면 완전수, 크면 초과수라고 합니다.

초과수는 무한하게 많이 생길 수밖에 없는데요.  실제 증명에 의하면, 초과수의 분포가 숫자 범위가 커지면서 크게 늘어나지도 않고, 줄어들지도 않는다고 합니다.

초과수는 다음과 같은 경우가 있습니다.

1. 완전수의 배수들(당연히 자신들은 빼야합니다.)

2. 초과수의 배수들(초과수 자신들은 포함됩니다.)

초과수가 되기 위해서는 작은 소수들로 이루어진 숫자들이 필요합니다.

초과수 중에 가장 작은 수는 12인데요.  사실 12는 완전수 6의 배수입니다.

완전수는 다음과 같이 표현을 할 수 있습니다.

완전수 n에  k > 1 인 k를 곱하면, 

이 되어서 초과수가 됩니다.

예를 들어서 6은 1, 2, 3, 6 의 약수를 가집니다.  6의 k배인 수 6k는 k, 2k, 3k, 6k 의 약수를 당연히 가지고 있겠죠.  k > 1 이므로 이 이외에도 1이라는 약수를 더 가지므로, 초과수가 됩니다.  12는 완전수 6의 2배수입니다.  6의 약수인 1, 2, 3, 6 은 당연히 12의 약수이고, 2배수인 2, 4, 6, 12 역시 12의 약수입니다.  2, 4, 6, 12의 합이 24가 되고, 그 외에 1, 3이라는 약수가 더 있으므로 초과수가 되는 것이 당연합니다.

위 식은 n이 초과수인 경우에도 그대로 적용할 수 있기 때문에 당연히 초과수가 된다는 것을 알 수 있습니다.  이것을 이용하면 초과수를 찾아내는데 도움이 많이 되지 않을까 생각합니다.

사실 초과수들을 살펴보면, 12, 18, 24, 30, 36, 42, .. 와 같이 초반에 나오는 초과수들은 완전수 6의 배수들입니다.  20, 30, 40, 60, 80, ... 은 20 초과수의 배수죠.  56, 84, ... 는 완전수 28의 배수입니다.

그렇지만, 본 문제에서는 이 숫자를 알아내는 방법을 줄이는 것만으로는 전체적인 속도를 줄일 수는 없습니다.

두개의 초과수의 합으로 표현할 수 없는 숫자들을 찾아내는 것이 가장 큰 문제입니다.

만약 초과수의 합으로 표현할 수 없는 숫자의 한계가 없었다면, 컴퓨터로 모든 경우를 찾는 것은 불가능했을겁니다.  한계가 주어졌으므로, 저는 초과수의 합으로 표현될 수 있는 경우를 모두 찾아내서, 해당 한계안의 숫자에서 빼주었습니다.  아마 이것이 가장 현실적인 방법이 아니었을까 생각합니다.  (곱하기라면 인수분해가 가능하지만, 더하기는 그 경우의 수가 한정할 수 없으므로)

그래서 만들어진 소스는 다음과 같습니다.

#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;
}