約数和配列を用いて婚約数
友愛数は約数の和を調べましたが、約数に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追記)
ソースコードを少し整理しました。
(2021/10/5追記)
配列を更に大きくして10億以下の範囲で求めました。10億以下同士の友愛数は168組あり、最大の組は(820888964 921943035)でした。
(2021/11/10追記)
友愛数と同じく、AWS で m5.8xlarge インスタンスを使って100億以下の婚約数を探索しました。100億以下の婚約数は364組あり、最大は(8816125724 8954833635)でした。
100億以下の範囲においても婚約数の個数は364組と、友愛数の1391組に比べると1/3程度しかありません。上述した婚約数は友愛数よりも稀少であるという予想は正しいんでしょうかね。正しいとして、なぜそうなるかも不思議です。直感的には同じくらいの数だけありそうな気がするんですがね。
約数和配列を用いずに婚約数を求める
(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 : 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 / 2; i++ ) {
if( n % i == 0 ) {
n2 += i;
}
}
if( n2 <= n ) {
continue;
}
n3 = 0;
for( i = 2; i <= n2 / 2; i++ ) {
if( n2 % i == 0 ) {
n3 += i;
}
}
if( n3 == n ) {
printf( "%d %d\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万以上の婚約数は数が多いので別ファイルとして置いておきます。