社交数を求める

社交数

社交数というのは友愛数を拡張したもので、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)

(2020/9/13追記)

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


#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]; 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 );
}