倍積完全数

倍積完全数

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

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

#define    MAX_ARRAY    (100000000)

int array[MAX_ARRAY];

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

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

    /*    MAX_ARRAY分ごとの整数区間を調べる    */
    for( base = 2; 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( "%d\n", base + n );
        }
    }

    return( 0 );
}

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

(2012/2/16追記)

以前ここでは「n倍完全数」と書いていましたが「倍積完全数」と呼ぶのが正しいようです。また、n倍完全数とはn自身も加えて計算するそうなので、一般の完全数は2倍完全数となり、これまでこのページで呼んでいたn倍完全数はn+1倍完全数と呼ぶのが正しいようです。これらの点を修正しました。

また、メモリが潤沢に使用できるようになったので配列のサイズを1億に増やしました。探索範囲を10億以下に広げたところ、3倍完全数として459818240が、4倍完全数として142990848が見つかりました。


あおやぎのさいと2.0初歩の整数論プログラミング