友愛数判定
スポンサーリンク
友愛数判定に挑戦してみる。
友愛数とは例えば２２０や２８４などで２２０の約数は1,2,4,5,10,11,20,22,44,55,110で合計すると２８４。同様に２８４の約数は1,2,4,71,142で合計で２２０である。
このように約数が互いを示す数のことを友愛数とよび、ピタゴラスが発見した。しかしながら２組目はピエール･ド・フェルマーが１６３６年に17296と18416を発見するまで見つかっておらず、数学者など数を愛する人たちに神秘的な数としてよく数学者の物語などに
登場する。最近では「博士の愛した数式」等に出てきてちょっとした話題になった。
現在数百種類見つかっている。因みに現在の２番目に小さい数は1184と1210で１６歳のイタリア人学生が見つけた。
さて、ともかくまず約数を判定するコードが無ければならない。
掛ける数と掛けられる数をiとjとし、
二重ループでi*j==Nの時にiとjを足すことにする。
/*約数判定*/
#include<stdio.h>
#define N 18416
main()
{
int i,j;/*jが掛けられるほう*/
int divsum=0;
for(i=1;i<N&&i*i<=N;i++)/*i*iがNを超えたらそれ以上は鏡なので無意味*/
{
for(j=N;j>=i;j--)
{
if(N==i*j)
{
printf("%d,%d\n",i,j);
if(i!=j)/* iとjが同じなら同じ数字を二回足してしまう*/
{divsum=divsum+i+j;}
else
{divsum=divsum+i;}
}
}
}
divsum-=N;/*約数合計にNを含んでいるので消す*/
printf("%d\n",divsum);
}
結果
Nを284
1,284
2,142
4,71
220
Nを220
1,220
2,110
4,55
5,44
10,22
11,20
284
Nを18416
1,18416
2,9208
4,4604
8,2302
16,1151
17296何とかうまくいっている模様。
コツはi==jになってしまったらどちらか一方を足すことにすることと、
最後に必ず1*N=NというNが入ってしまうので引いてあげる。
さて、次に２つの約数を混ぜるにはどうしたらよいだろうか・・？
一番簡単なのは２つ並べて最後に２つが友愛数であるか判定する。
処理にオーバーヘッドがかかりすぎだが出来ないよりはずっといいのでとりあえずやってみる。
/*友愛数判定*/
#include<stdio.h>
#define N 18416
#define M 17296
main()
{
int i,j;/*jが掛けられるほう*/
int divsum=0,divsum2=0;
for(i=1;i<N&&i*i<=N;i++)/*i*iがNを超えたらそれ以上は鏡なので無意味*/
{
for(j=N;j>=i;j--)
{
if(N==i*j)
{
printf("%d,%d\n",i,j);
if(i!=j)/* iとjが同じなら同じ数字を二回足してしまう*/
{divsum=divsum+i+j;}
else
{divsum=divsum+i;}
}
}
}
divsum-=N;/*約数合計にNを含んでいるので消す*/
printf("%d\n\n",divsum);
for(i=1;i<M&&i*i<=M;i++)/*i*iがNを超えたらそれ以上は鏡なので無意味*/
{
for(j=M;j>=i;j--)
{
if(M==i*j)
{
printf("%d,%d\n",i,j);
if(i!=j)/* iとjが同じなら同じ数字を二回足してしまう*/
{divsum2=divsum2+i+j;}
else
{divsum2=divsum2+i;}
}
}
}
divsum2-=M;/*約数合計にNを含んでいるので消す*/
printf("%d\n",divsum2);
if(divsum==M&&divsum2==N)
puts("友愛数です。");
else if(divsum==M||divsum==N)
puts("準友愛数です。");
else
puts("友愛数ではない");
}
結果
1,18416
2,9208
4,4604
8,2302
16,1151
17296
1,17296
2,8648
4,4324
8,2162
16,1081
23,752
46,376
47,368
92,188
94,184
18416
友愛数です。まあ、何とかうまく動いた。
次は１から順に調べていきたい・・何か新しい友愛数があるかも・・（99.9999.....％）無いが。ｗ
とりあえずこの駄コードでCPU暖房機を生産する。
/*友愛数判定*/
#include<stdio.h>
#define LIMIT 1211
main()
{
int i,j;
int divsum=0,divsum2=0;
int N,M;
for(N=1;N<=LIMIT;N++)
{
for(M=1;M<=LIMIT;M++)
{
for(i=1;i<N&&i*i<=N;i++)
{
for(j=N;j>=i;j--)
{
if(N==i*j)
{
if(i!=j)
{divsum=divsum+i+j;}
else
{divsum=divsum+i;}
}
}
}
divsum-=N;
for(i=1;i<M&&i*i<=M;i++)
{
for(j=M;j>=i;j--)
{
if(M==i*j)
{
if(i!=j)
{divsum2=divsum2+i+j;}
else
{divsum2=divsum2+i;}
}
}
}
divsum2-=M;
if((divsum==M&&divsum2==N)&&N!=M)
printf("%dと%dは友愛数です。",N,M);
divsum=0;
divsum2=0;/*初期化*/
}
}
}
結果
220と284は友愛数です。284と220は友愛数です。1184と1210は友愛数です。1210と1184は
友愛数です。 -- Press any key to exit (Input "c" to continue) --入れ子が多すぎて他人の読む限界をおそらく超えてしまったコードになったが思考過程を辿っていけば当たり前に書ける駄コードなので解説は抜いた。
人前に出す必要があるなら関数にして分かりやすく記述する必要がある。
自分用コードなので処理の手間を少しでも短くするほうを選んだ。
まぁ１２１１までの中に新たな友愛数は無いことは分かった。
