友愛数

友愛数

友愛数とは、約数の和がお互いの数自身になる数の組を言います。例えば220と284は友愛数です。220は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110を約数として持ちその和は284となり、284は約数として1, 2, 4, 71, 142となりその和は220となり友愛数であることが分かります。

プログラムは完全数を求めた約数和配列を利用しています。ただし、完全数はその数自身で判定が可能だったので配列を繰り返し使用することで大きな値まで探索が可能でしたが、友愛数は二つの数が関係することからこの方法を使用することが出来ません。大きな範囲を探索するには更なるプログラムの工夫が必要です。


#include <stdio.h>

#define ARRAY_SIZE_MAX   (100000000)

int array[ARRAY_SIZE_MAX];

int main( int ac, char *av[] )
{
    int n, n2, i;

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

    /*  約数の和を求める    */
    for( n = 1; n < ARRAY_SIZE_MAX / 2; n++ ) {
        for( i = 2; i * n < ARRAY_SIZE_MAX; i++ )
            array[i * n] += n;
    }

    /*  約数の和が互いの数自身になれば友愛数である  */
    for( n = 1; n < ARRAY_SIZE_MAX; n++ ) {
        n2 = array[n];
        if( n2 < ARRAY_SIZE_MAX && n < n2 && array[n2] == n )
            printf( "%d %d\n", n, n2 );
    }

    return( 0 );
}

両方ともに1千万以下の友愛数は全部で100組見つかりました。これまでに見つかった友愛数は全て偶数同士もしくは奇数同士らしいのですが、実際1千万以下の範囲で見つかった100組も全て偶数もしくは奇数同士でした。偶数と奇数の組み合わせの友愛数があるかどうかはまだ分かっていないそうです。

(2012/2/16追記)

メモリが潤沢に使用できるようになりましたので、配列を大きくして1億以下まで求めるようにしました。1億以下同士の友愛数は231組ありました。

(2020/4/25追記)

ソースコードを少し整理しました。

1億以下同士での友愛数一覧
yuuailist100000000.txt(4KB)

(2020/9/9追記)

順序が逆になってしまいましたが、約数和配列を用いず、常に約数を求めながら友愛数を求める版を作りました。速度的には非常に遅くなってしまいますが、探索範囲を配列サイズに制限されないというメリットがあります。


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

int main( int ac, char *av[] )
{
    int n, min_n, max_n;
    int i, n2, n3;

    /*  コマンドラインから友愛数探索範囲を決定する    */
    if( ac < 3 ) {
        printf( "usage : yuuai min_n max_n\n" );
        return( 1 );
    }
    min_n = strtol( av[1], NULL, 10 );
    max_n = strtol( av[2], NULL, 10 );

    /*  探索範囲の数を調べる    */
    for( n = min_n; n <= max_n; n++ ) {
        n2 = 0;
        for( i = 1; i < n; i++ ) {
            if( n % i == 0 ) {
                n2 += i;
            }
        }
        if( n2 <= n ) {
            continue;
        }

        n3 = 0;
        for( i = 1; i < n2; i++ ) {
            if( n2 % i == 0 ) {
                n3 += i;
            }
        }
        if( n3 == n ) {
            printf( "%d %d\n", n, n2 );
        }
    }

    return( 0 );
}