社交数を求める

約数和配列を用いて社交数を求める

社交数というのは友愛数を拡張したもので、aの約数の和がbに、bの約数の和がcに、cの約数の和がaになるような3数の組を言います。

#include <stdio.h>

#define ARRAY_SIZE_MAX   (100000000)
#define LIST_MAX   (100)

int array[ARRAY_SIZE_MAX];

int main( int ac, char *av[] )
{
    int n, n_list[LIST_MAX], i, j;

    /*  配列を初期化する    */
    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++ ) {
        n_list[0] = n;
        for( i = 1; i < LIST_MAX; i++ ) {
            n_list[i] = array[n_list[i - 1]];
            if( n_list[i] >= ARRAY_SIZE_MAX || n_list[i] < n ) {
                break;
            }
            if( n_list[i] == n_list[0] ) {
                if( i > 2 ) {
                    for( j = 0; j < i; j++ ) {
                        printf( "%d ", n_list[j] );
                    }
                    printf( "\n" );
                }
                break;
            }
        }
    }

    return( 0 );
}

1千万以下の範囲を調べてみましたが、残念ながら社交数は見つかりませんでした。実は社交数は未だに一組も見つかっていないそうです。だからといって社交数が存在しないと証明されてもいないそうです。ちなみに4数での社交数などは見つかっているそうです。

(2012/2/16追記)

こちらも、配列を大きくして1億以下まで求めるようにしました。しかし、やはり社交数は一組も見つかりませんでした。

(2020/4/25追記)

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

(2020/9/12追記)

3組以上の場合も社交数というそうなので、プログラムを修正しました。実行したところ、以下の社交数が見つかりました。

(12496 14288 15472 14536 14264), (14316 19116 31704 47616 83328 177792 295488 629072 589786 294896 358336 418904 366556 274924 275444 243760 376736 381028 285778 152990 122410 97946 48976 45946 22976 22744 19916 17716), (1264460 1547860 1727636 1305184), (2115324 3317740 3649556 2797612), (2784580 3265940 3707572 3370604), (4938136 5753864 5504056 5423384), (7169104 7538660 8292568 7520432), (18048976 20100368 18914992 19252208), (18656380 20522060 28630036 24289964), (28158165 29902635 30853845 29971755), (46722700 56833172 53718220 59090084), (81128632 91314968 96389032 91401368)

(2021/10/5追記)

配列を更に大きくして10億以下の範囲で求めました。更に以下の社交数が見つかりました。

(174277820 205718020 262372988 210967684), (209524210 246667790 231439570 230143790), (330003580 363003980 399304420 440004764), (498215416 506040584 583014136 510137384)

(2021/11/10追記)

友愛数と同じく、AWS で m5.8xlarge を使って100億以下の社交数を探索しました。新たに以下の社交数が見つかりました。

(805984760 1268997640 1803863720 2308845400 3059220620 3367978564 2525983930 2301481286 1611969514), (1095447416 1259477224 1156962296 1330251784 1221976136 1127671864 1245926216 1213138984), (1236402232 1369801928 1603118392 1412336648), (1276254780 2299401444 3071310364 2303482780 2629903076 2209210588 2223459332 1697298124), (1799281330 2267877710 2397470866 1954241390), (2387776550 2497625050 2550266150 2506553050), (2717495235 3509525565 3977471043 3100575933), (2879697304 3320611496 3364648984 3147575336), (3705771825 3890616975 4298858865 4659093135), (4424606020 5186286908 4720282996 4993345292), (4823923384 5708253896 5513075704 5196238856), (5373457070 5406735730 5575049870 5983131730), (8653956136 9890235704 9468980296 9237894104)

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

(2020/9/13追記)

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

(2021/10/4追記)

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

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

#define LIST_MAX   (100)

int main( int ac, char *av[] )
{
    int n, min_n, max_n;
    int n_list[LIST_MAX], i, j;

    /*  コマンドラインから社交数探索範囲を決定する    */
    if( ac < 3 ) {
        printf( "usage : syakou 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++ ) {
        n_list[0] = n;
        for( i = 1; i < LIST_MAX; i++ ) {
            n_list[i] = 0;
            for( j = 1; j <= n_list[i - 1] / 2; j++ ) {
                if( n_list[i - 1] % j == 0 ) {
                    n_list[i] += j;
                }
            }
            if( n_list[i] < n ) {
                break;
            }
            if( n_list[i] == n_list[0] ) {
                if( i > 2 ) {
                    for( j = 0; j < i; j++ ) {
                        printf( "%d ", n_list[j] );
                    }
                    printf( "\n" );
                }
                break;
            }
        }
    }

    return( 0 );
}

社交数の一覧

これまでに見つかった社交数の一覧を載せておきます。なお、このページで見つけた社交数がこれだけということで、世界ではもっと多くの社交数が見つかっています。

4個組の社交数

5個組の社交数

8個組の社交数

9個組の社交数

28個組の社交数