婚約数を求める

婚約数

友愛数は約数の和を調べましたが、約数に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 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 = 2; 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を加えてないことからそんな気もしますが、理由を証明しろと言われても難しいですね。1千万以下の範囲では40組の婚約数が見つかりました。友愛数の100組よりも少ないですが、常に婚約数の方が少ないのかどうかは気になるところです。

(2012/2/16追記)

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

(2020/4/25追記)

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

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

(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 : konyaku 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 = 2; i < n; i++ ) {
            if( n % i == 0 ) {
                n2 += i;
            }
        }
        if( n2 <= n ) {
            continue;
        }

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

    return( 0 );
}