婚約数

婚約数

友愛数は約数の和を調べましたが、約数に1を加えずに成り立つものを婚約数と言います。例えば48と75は婚約数です。48の1を除いた約数は2,3,4,6,8,12,16,24でその和は75です。75の1を除いた約数は3,5,15,25でその和は48です。

プログラムは友愛数を探すプログラムで1を足さなくしただけで、大変簡単な改変です。

#include <stdio.h>

#define MAX_ARRAY   (100000000)

int array[MAX_ARRAY];

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

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

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

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

    return( 0 );
}

婚約数は友愛数とは逆で奇数と偶数の組み合わせしか見つかっていないそうです。1を加えてないことからそんな気もしますが、理由を証明しろと言われても難しいですね。1千万以下の範囲では40組の婚約数が見つかりました。友愛数の100組よりも少ないですが、常に婚約数の方が少ないのかどうかは気になるところです。

(2012/2/16追記)

こちらも、配列を大きくして1億以下まで求めるようにしました。1億以下同士の婚約数は73組ありました。

1億以下同士での婚約数一覧
konyakulist100000000.txt(2KB)

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