約数和配列を用いて友愛数を求める
友愛数とは、約数の和がお互いの数自身になる数の組を言います。例えば220と284は友愛数です。220は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110を約数として持ちその和は284となり、284は約数として1, 2, 4, 71, 142となりその和は220となり友愛数であることが分かります。
プログラムは完全数 - 約数和配列で使った約数和配列を利用しています。ただし、完全数はその数自身で判定が可能だったので配列を繰り返し使用することで大きな値まで探索が可能でしたが、友愛数は二つの数が関係することからこの方法を使用することが出来ません。大きな範囲を探索するには更なるプログラムの工夫が必要です。
#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 = 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++ ) {
n2 = array[n];
if( n2 < ARRAY_SIZE_MAX && n < n2 && array[n2] == n )
printf( "%d %d\n", n, n2 );
}
return( 0 );
}
両方ともに1千万以下の友愛数は全部で100組見つかりました。これまでに見つかった友愛数は全て偶数同士もしくは奇数同士らしいのですが、実際1千万以下の範囲で見つかった100組も全て偶数もしくは奇数同士でした。偶数と奇数の組み合わせの友愛数があるかどうかはまだ分かっていないそうです。
(2012/2/16追記)
メモリが潤沢に使用できるようになりましたので、配列を大きくして1億以下まで求めるようにしました。1億以下同士の友愛数は231組ありました。
(2020/4/25追記)
ソースコードを少し整理しました。
(2021/10/5追記)
配列を更に大きくして10億以下の範囲で求めました。10億以下同士の友愛数は564組あり、最大の組は(957871508 998051692)でした。
10億以下ではメモリを4GB(4bytes x 10億)使用しましたが、100億以下となると8バイト整数を使用するため80GBものメモリが必要になってしまい、そうした環境を調達するのは難しそうです。将来、メモリが更に安価になったら挑戦してみたいです。
ちなみに素数を求める - エラトステネスのふるいを繰り返し使うのように約数和配列を繰り返し使う方法は、友愛数の組の両方が同じ約数和配列に収まってる場合のみしか求められないため不適です。大抵の友愛数は近しい範囲の値に収まっているのですが、例外があり得ないとは言い切れません。
(2021/11/10追記)
クラウドサービスを使えば巨大なメモリを搭載した環境も手軽に調達できることに気づいたので、AWS にて m5.8xlarge(メモリ128GB)のインスタンスを作成して100億以下の範囲で友愛数を探索しました。1時間あたり1.984 USDとなかなか痺れる単価ですが、せいぜい数時間の利用ですから実際にはそれほど厳しいわけではありません。
100億以下同士の友愛数は1391組あり、最大の組は(9958985128 9994662872)でした。
約数和配列を用いずに友愛数を求める
(2020/9/9追記)
順序が逆になってしまいましたが、約数和配列を用いず、常に約数を求めながら友愛数を求める版を作りました。速度的には非常に遅くなってしまいますが、探索範囲を配列サイズに制限されないというメリットがあります。
(2021/10/4追記)
約数を調べる際、n/2までしか調べなくていいことをうっかりしてたので修正しました。
#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 : yuuai 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 = 1; i <= n / 2; i++ ) {
if( n % i == 0 ) {
n2 += i;
}
}
if( n2 <= n ) {
continue;
}
n3 = 0;
for( i = 1; i <= n2 / 2; i++ ) {
if( n2 % i == 0 ) {
n3 += i;
}
}
if( n3 == n ) {
printf( "%d %d\n", n, n2 );
}
}
return( 0 );
}
友愛数の一覧
双方が10万以下の友愛数は以下の通りです。
(220 284) (1184 1210) (2620 2924) (5020 5564) (6232 6368) (10744 10856) (12285 14595) (17296 18416) (63020 76084) (66928 66992) (67095 71145) (69615 87633) (79750 88730)
10万以上の友愛数は数が多いので別ファイルとして置いておきます。