婚約数を求める

約数和配列を用いて婚約数

友愛数は約数の和を調べましたが、約数に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>
#include <stdlib.h>

#define DIVISORSUMLIST_SIZE_MAX   (100000000)

long long divisorsumlist[DIVISORSUMLIST_SIZE_MAX];

int main( int ac, char *av[] )
{
    long long divisorsumlistsize, i, j, base, n, n2, tmp, min_n, max_n;

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

    /*  DIVISORSUMLIST_SIZE_MAX / 2 ごとの整数区間を調べる   */
    /*  約数和配列自体は最大 DIVISORSUMLIST_SIZE_MAX まで求める(ペア数字が配列内に収まりやすくするため) */
    for( base = min_n; base <= max_n; base += DIVISORSUMLIST_SIZE_MAX / 2 ) {
        /*  整数区間配列の大きさを決める    */
        if( max_n - base + 1 > DIVISORSUMLIST_SIZE_MAX / 2 )
            divisorsumlistsize = DIVISORSUMLIST_SIZE_MAX/ 2 ;
        else
            divisorsumlistsize = max_n - base + 1;

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

        /*  約数の和を求める    */
        for( i = 2; i <= ( base + divisorsumlistsize * 2 ) / 2; i++ ) {
            j = ( base + i - 1 ) / i * i;
            if( j < i * 2 )
                j = i * 2;
            for( ; j < base + divisorsumlistsize * 2; j += i )
                divisorsumlist[j - base] += i;
        }

        /*  約数の和が互いの数自身になれば婚約数である  */
        for( i = 0; i < divisorsumlistsize; i++ ) {
            n = base + i;
            n2 = divisorsumlist[i];
            if( n2 <= n )
                continue;
            if( n2 < base + divisorsumlistsize * 2 ) {
                if( divisorsumlist[n2 - base] == n )
                    printf( "%lld %lld\n", n, n2 );
            }
            else {
                /*  配列の範囲外の場合は個別計算する  */
                tmp = 0;
                for( j = 2; j <= n2 / j; j++ ) {
                    if( n2 % j == 0 ) {
                        tmp += j;
                        if( n2 / j != j )
                            tmp += ( n2 / j );
                    }
                }
                if( n == tmp )
                    printf( "%lld %lld\n", n, n2 );
            }
        }
    }

    return( 0 );
}

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

(2012/2/16追記)

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

(2020/4/25追記)

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

(2021/10/5追記)

配列を更に大きくして10億以下の範囲で求めました。10億以下同士の友愛数は168組あり、最大の組は(820888964 921943035)でした。

(2021/11/10追記)

友愛数と同じく、AWS で m5.8xlarge インスタンスを使って100億以下の婚約数を探索しました。100億以下の婚約数は364組あり、最大は(8816125724 8954833635)でした。

100億以下の範囲においても婚約数の個数は364組と、友愛数の1391組に比べると1/3程度しかありません。上述した婚約数は友愛数よりも稀少であるという予想は正しいんでしょうかね。正しいとして、なぜそうなるかも不思議です。直感的には同じくらいの数だけありそうな気がするんですがね。

(2026/2/5追記)

友愛数のページにも追記しましたが、100億以下の計算時は一時的に int を long long に書き換えています。

(2026/3/13追記)

友愛数を求めると同様に、int を long long に変更し、ソースコードを整理し、約数和配列を繰り返し使用するように修正しました。

(2026/3/27追記)

単純な方法で約数和を求める処理を√nまでしか計算しないようにして高速化しました。

(2026/3/27追記その2)

友愛数を求めると同様に10億以下の一覧を更新しました。合わせて組の数も掲載しています。

約数和配列を用いずに婚約数を求める

(2020/9/9追記)

友愛数と同様に、約数和配列を用いない版を作りました。

(2021/10/4追記

約数を調べる際、n/2までしか調べなくていいことをうっかりしてたので修正しました。

(2026/3/27追記

int を long long に変更したのがこちらには反映されていませんでした。作業漏れです。

合わせて、単純な方法で約数和を求める処理を√nまでしか計算しないようにして高速化しました。

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

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

    /*  コマンドラインから探索範囲を決定する    */
    if( ac < 3 ) {
        fprintf( stderr, "usage : konyaku min_n max_n\n" );
        return( 1 );
    }
    min_n = strtoll( av[1], NULL, 10 );
    max_n = strtoll( av[2], NULL, 10 );
    if( min_n < 1 || max_n < 1 ) {
        fprintf( stderr, "bad parameter\n" );
        return( 1 );
    }

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

        if( n2 <= n )
            continue;

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

    return( 0 );
}

婚約数の一覧

双方が10万以下の婚約数は以下の通りです。

(48 75) (140 195) (1050 1925) (1575 1648) (2024 2295) (5775 6128) (8892 16587) (9504 20735) (62744 75495)

10万以上の婚約数は数が多いので別ファイルとして置いておきます。

• 1億以下(2KB)
• 10億以下(4KB)

婚約数の組の数一覧