Project Euler 問題21で、友愛数についての問題を解きました。友愛数に関する歴史や性質を紹介します。
友愛数の定義と例
定義
自然数 $n$ の真の約数（$n$ より小さい、$n$ を割り切る数）の和を $d(n)$ とする。$d(a) = b,\; d(b) = a,\; a \neq b$ のとき、$a$ と $b$ を友愛数（amicable numbers）と呼ぶ。
例
220 の真の約数は、1、2、4、5、10、11、20、22、44、55、110 であるため、$d(220) = 284$ となる。
284 の真の約数は、1、2、4、71、142 であるため、$d(284) = 220$ となる。
よって、220 と 284 は友愛数となる。
友愛数の個数
以下は、友愛数を求める C のプログラムです。
#include <stdio.h>
typedef unsigned long long int ull;
#define N 100000000
ull calc_sum_of_divisors(ull number)
{
ull sum;
ull i;
sum = 1; /* Add 1 (the first divisor) */
for (i = 2; i * i <= number; ++i) {
if ((number % i) == 0) {
if (i * i != number) {
sum += i;
sum += number / i;
} else {
sum += i;
}
}
}
return sum;
}
int main(void)
{
ull a, b;
for (a = 2; a <= N; ++a) {
b = calc_sum_of_divisors(a);
if ((b > a)&&(a == calc_sum_of_divisors(b))) {
printf("%lld %lld\n", a, b);
}
}
return 0;
}4行目で定義している N 以下の友愛数をすべて出力します。
このプログラムで、$10^8$ 程度までの友愛数を求めることができました。ただし、$10^8$ の場合で、私のパソコンで80分弱かかっています。$10^9$ にすると、数日かかります。
$10^8$ 以下までの友愛数の組の数です。
| $X$ | $X$ 以下の友愛数の組 |
| $10^3$ | $1$ |
| $10^4$ | $5$ |
| $10^5$ | $13$ |
| $10^6$ | $42$ |
| $10^7$ | $108$ |
| $10^8$ | $236$ |
友愛数の発見の歴史
一番小さい友愛数の組である 220 と 284 は、古代ギリシャから知られていました。聖書にも 220 と 284 という数字が出てくるようです。
フェルマー（1607-1665）、デカルト（1596-1650）、オイラー（1707－1783）ら著名な数学者も、友愛数を見つけています。
一方、計算機があったわけではないため網羅的な計算ができていませんでした。2番目の友愛数である 1184 と 1210 は、1866年に学生が見つけています。
友愛数についての疑問
- 友愛数は、無限にあると予想されていますが、証明はされていません。
- 最初の236組（=472個）の友愛数には、5の倍数が208個（44.1%）もあります。この傾向は続きますが、理由は分かっていません。
- 一方が平方数である友愛数の組は、まだ見つかっていません。
- 互いに素となる友愛数の組が存在するか分かっていません。
最後に
この記事のいくつかの内容は、「プライムナンバーズ」（David Wells著 伊知地宏監訳 オライリージャパン 2008年）の「友愛数」の項を参考にしました。
220 と 284 はどちらも、何気なく見過ごしてしまいますが、興味深い性質があることが分かりました。
1億までの友愛数
友愛数の組で、一方が1億より小さいものは236組あります。以下となります。
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
100485 124155
122265 139815
122368 123152
141664 153176
142310 168730
171856 176336
176272 180848
185368 203432
196724 202444
280540 365084
308620 389924
319550 430402
356408 399592
437456 455344
469028 486178
503056 514736
522405 525915
600392 669688
609928 686072
624184 691256
635624 712216
643336 652664
667964 783556
726104 796696
802725 863835
879712 901424
898216 980984
947835 1125765
998104 1043096
1077890 1099390
1154450 1189150
1156870 1292570
1175265 1438983
1185376 1286744
1280565 1340235
1328470 1483850
1358595 1486845
1392368 1464592
1466150 1747930
1468324 1749212
1511930 1598470
1669910 2062570
1798875 1870245
2082464 2090656
2236570 2429030
2652728 2941672
2723792 2874064
2728726 3077354
2739704 2928136
2802416 2947216
2803580 3716164
3276856 3721544
3606850 3892670
3786904 4300136
3805264 4006736
4238984 4314616
4246130 4488910
4259750 4445050
4482765 5120595
4532710 6135962
4604776 5162744
5123090 5504110
5147032 5843048
5232010 5799542
5357625 5684679
5385310 5812130
5459176 5495264
5726072 6369928
5730615 6088905
5864660 7489324
6329416 6371384
6377175 6680025
6955216 7418864
6993610 7158710
7275532 7471508
7288930 8221598
7489112 7674088
7577350 8493050
7677248 7684672
7800544 7916696
7850512 8052488
8262136 8369864
8619765 9627915
8666860 10638356
8754130 10893230
8826070 10043690
9071685 9498555
9199496 9592504
9206925 10791795
9339704 9892936
9363584 9437056
9478910 11049730
9491625 10950615
9660950 10025290
9773505 11791935
10254970 10273670
10533296 10949704
10572550 10854650
10596368 11199112
10634085 14084763
10992735 12070305
11173460 13212076
11252648 12101272
11498355 12024045
11545616 12247504
11693290 12361622
11905504 13337336
12397552 13136528
12707704 14236136
13671735 15877065
13813150 14310050
13921528 13985672
14311688 14718712
14426230 18087818
14443730 15882670
14654150 16817050
15002464 15334304
15363832 16517768
15938055 17308665
16137628 16150628
16871582 19325698
17041010 19150222
17257695 17578785
17754165 19985355
17844255 19895265
17908064 18017056
18056312 18166888
18194715 22240485
18655744 19154336
20014808 21457192
20022328 22823432
20308995 20955645
21448630 23030090
22227075 24644925
22249552 25325528
22508145 23111055
22608632 25775368
23358248 25233112
23389695 25132545
23628940 27428276
24472180 30395276
25596544 25640096
25966832 26529808
26090325 26138475
28118032 28128368
28608424 29603576
30724694 32174506
30830696 31652704
31536855 32148585
31818952 34860248
32205616 34352624
32642324 35095276
32685250 34538270
33501825 36136575
34256222 35997346
34364912 34380688
34765731 36939357
35115795 43266285
35361326 40117714
35373195 40105845
35390008 39259592
35472592 36415664
37363095 45663849
37784810 39944086
37848915 39202605
38400512 38938288
38637016 40678184
38663950 43362050
38783992 41654408
38807968 40912232
43096904 46715896
44139856 44916944
45263384 46137016
46237730 61319902
46271745 49125375
46521405 53011395
46555250 55880590
46991890 48471470
48639032 52967368
48641584 48852176
49215166 55349570
50997596 51737764
52695376 56208368
56055872 56598208
56512610 75866014
56924192 64562488
58580540 70507972
59497888 61953512
63560025 65003175
63717615 66011985
66595130 74824390
66854710 71946890
67729064 69439576
67738268 79732132
68891992 78437288
71015260 85458596
71241830 78057370
72958556 74733604
73032872 78469528
74055952 78166448
74386305 87354495
74769345 82824255
75171808 77237792
75226888 81265112
78088504 88110536
78447010 80960990
79324875 87133365
80422335 82977345
82633005 104177619
83135650 85603550
84521745 107908335
84591405 89590995
86158220 99188788
87998470 102358010
88144630 102814490
89477984 92143456
90437150 94372450
91996816 93259184
93837808 99899792
95629904 97580944
95791430 115187002
96304845 96747315
97041735 97945785
