n倍完全数を探す

約数和配列を利用して、約数の和が元の数のn倍になるような数を探してみます。約数の和がその数自身より小さいものを不足数、大きいものを過剰数と呼ぶそうです。という事は全ての自然数は不足数、完全数、過剰数のどれかに分類されることになります。n倍完全数は過剰数の特別なものになります。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define    MAX_ARRAY    (1000000)

unsigned long long    array[MAX_ARRAY];

void main( int ac, char *av[] )
{
    unsigned long long  base, arraysize, m, n, min_n, max_n, i;

    /*  コマンドラインからm及び完全数探索範囲を決定する    */
    if( ac < 4 )
        return;
    m = strtouq( av[1], NULL, 10 );
    min_n = strtouq( av[2], NULL, 10 );
    if( min_n < 2 )
        min_n = 2;
    max_n = strtouq( av[3], NULL, 10 );

    /*    MAX_ARRAY分ごとの整数区間を調べる    */
    for( base = min_n; base < max_n; base += MAX_ARRAY ) {
        /*    整数区間配列の大きさを決める    */
        if( max_n - base + 1 > MAX_ARRAY )
            arraysize = MAX_ARRAY;
        else
            arraysize = max_n - base + 1;

        /*    配列を初期化する    */
        for( i = 0; i < arraysize; i++ )
            array[i] = 0;

        /*    約数の和を求める    */
        for( n = 1; n < ( base + arraysize ) / 2; n++ ) {
            if( base <= n )
                i = n * 2;
            else if( base % n == 0 )
                i = base;
            else
                i = ( base / n + 1 ) * n;
            for( ; i < base + arraysize; i += n )
                array[i - base] += n;
        }

        /*    約数の和とその数自身のm倍が等しければ完全数である    */
        for( n = 0; n < arraysize; n++ ) {
            if( array[n] == m * ( base + n ) )
                printf( "%qu\n", base + n );
        }
    }
}

1億以下の数について10倍完全数までを探索したところ、2倍完全数として120、672、523776が、3倍完全数として30240、32760、2178540、23569920、45532800が見つかりました。4倍以上の完全数は見つかっていません。直感的にも倍数の大きな完全数は存在しにくいだろうと思われますので、この結果にも納得がいきます。