Дружественные числа

Дру́жественные чи́сла — два различных натуральных числа, для которых сумма всех собственных делителей первого числа равна второму числу и наоборот, сумма всех собственных делителей второго числа равна первому числу. То есть, пару натуральных чисел $M,N$ называют дружественной, если:

$m_{1}+m_{2}+\ldots +m_{k}=N,$

$n_{1}+n_{2}+\ldots +n_{l}=M,$

где $m_{1},m_{2},...m_{k}$ — делители числа $M$, $n_{1},n_{2},...n_{l}$ — делители числа $N$.

Большой важности для теории чисел эти пары не представляют, но являются любопытным элементом занимательной математики.

Иногда частным случаем дружественных чисел считаются совершенные числа: каждое совершенное число дружественно себе.

Если учитывать все делители, получим: $\sigma (M)-M=N$ или $\sigma (M)=M+N=\sigma (N)$ другое определение дружественных чисел, эквивалентное данному. Два числа называются дружественной парой, если они имеют одинаковую сумму всех своих делителей, которая равна сумме этих чисел.

Аналогично, три числа образуют дружественную тройку, если они имеют одинаковую сумму всех своих делителей, которая равна сумме этих чисел. $\sigma (M)=\sigma (N)=\sigma (K)=M+N+K$.

История

Дружественные числа были открыты последователями Пифагора; правда, им удалось найти только одну пару дружественных чисел — 220 и 284.

• Список делителей для 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, — их сумма равна 284.
• Список делителей для 284: 1, 2, 4, 71 и 142, — и сумма равна 220.

Примерно в 850 году арабский астроном и математик Сабит ибн Курра предложил формулу для нахождения некоторых пар дружественных чисел. Его формула позволила найти две новые пары дружественных чисел:

• 17 296 и 18 416;
• 9 363 584 и 9 437 056.

В XVIII веке Эйлер нашёл достаточный критерий построения пар дружественных чисел, и в его списке было уже 90 пар. Правда, этот критерий охватывает не все пары: например, пару (1184, 1210) Эйлер не заметил — её обнаружили уже в XIX веке. В XX веке компьютеры помогли найти десятки миллионов пар. Но эффективного общего способа нахождения всех таких пар нет до сих пор.

Первые пары

Пары дружественных чисел образуют последовательность A063990 в OEIS, причём числа, которые в своей дружественной паре являются меньшими, собраны в последовательность A002025, а бо́льшие - A002046. Суммы чисел в каждой паре образуют последовательность A180164. Примечательно, что все такие суммы, слагаемые где чётны, вплоть до $1362660800=2^{6}\cdot 5^{2}\cdot 31\cdot 83\cdot 331$ (сумма $666030256$ и $696630544$) делятся на $9$. Суммы, не делящиеся на $9$, находятся в A291550.

1. 220 и 284 (Пифагор, около 500 до н. э.)
2. 1184 и 1210 (Паганини, 1866)
3. 2620 и 2924 (Эйлер, 1747)
4. 5020 и 5564 (Эйлер, 1747)
5. 6232 и 6368 (Эйлер, 1750)
6. 10 744 и 10 856 (Эйлер, 1747)
7. 12 285 и 14 595 (Браун, 1939)
8. 17 296 и 18 416 (Ибн ал-Банна, около 1300; Фариси, около 1300; Ферма, 1636)
9. 63 020 и 76 084 (Эйлер, 1747)
10. 66 928 и 66 992 (Эйлер, 1750)
11. 67 095 и 71 145 (Эйлер, 1747)
12. 69 615 и 87 633 (Эйлер, 1747)
13. 79 750 и 88 730 (Рольф (Rolf), 1964)
14. 100 485 и 124 155
15. 122 265 и 139 815
16. 122 368 и 123 152
17. 141 664 и 153 176
18. 142 310 и 168 730
19. 171 856 и 176 336
20. 176 272 и 180 848
21. 185 368 и 203 432
22. 196 724 и 202 444
23. 280 540 и 365 084
24. 308 620 и 389 924
25. 319 550 и 430 402
26. 356 408 и 399 592
27. 437 456 и 455 344
28. 469 028 и 486 178
29. 503 056 и 514 736
30. 522 405 и 525 915
31. 600 392 и 669 688
32. 609 928 и 686 072
33. 624 184 и 691 256
34. 635 624 и 712 216
35. 643 336 и 652 664
36. 667 964 и 783 556
37. 726 104 и 796 696
38. 802 725 и 863 835
39. 879 712 и 901 424
40. 898 216 и 980 984
41. 947 835 и 1 125 765
42. 998 104 и 1 043 096
43. и т. д.

Способы построения

Формула Сабита ибн Курры

Если для натурального числа $n>1$ все три числа:

$p=3\times 2^{n-1}-1$,

$q=3\times 2^{n}-1$,

$r=9\times 2^{2n-1}-1$,

являются простыми, то числа $2^{n}pq$ и $2^{n}r$ образуют пару дружественных чисел.

Эта формула даёт пары (220, 284), (17 296, 18 416) и (9 363 584, 9 437 056) соответственно для $n=2,\;4,\;7$, но больше никаких пар дружественных чисел, которые могли бы быть получены по этой формуле для $n<20~000,$ не существует.

Формула Эйлера

Эйлер расширил формулу Сабита ибн Курры. Если для натуральных $n>m$ все три числа:

$p=(2^{n-m}+1)\times 2^{m}-1$,

$q=(2^{n-m}+1)\times 2^{n}-1$,

$r=(2^{n-m}+1)^{2}\times 2^{m+n}-1$,

являются простыми, то числа $2^{n}pq$ и $2^{n}r$ образуют пару дружественных чисел. Формула Сабита ибн Курры получается из формулы Эйлера подстановкой $m=n-1$. Формула Эйлера добавила к списку дружественных чисел всего 2 пары: $(m,n)=(1,8),(29,40).$

Метод Вальтера Боро

Если для пары дружественных чисел вида $A=au$ и $B=as$ числа $s$ и $p=u+s+1$ являются простыми, причём $a$ не делится на $p$, то при всех натуральных $n$, при которых оба числа $q_{1}=(u+1)p^{n+1}-1$ и $q_{2}=(u+1)(s+1)p^{n}-1$ просты, числа $B_{1}=Ap^{n}q_{1}$ и $B_{2}=ap^{n}q_{2}$ — дружественные.

Открытые проблемы

Неизвестно, конечно ли или бесконечно количество пар дружественных чисел. На апрель 2016 года известно более 1 000 000 000 пар дружественных чисел. Все они состоят из чисел одинаковой чётности.

Неизвестно, существует ли чётно-нечётная пара дружественных чисел.

Также неизвестно, существуют ли взаимно простые дружественные числа, но если такая пара дружественных чисел существует, то их произведение должно быть больше 10⁶⁷.

Список пар дружественных чисел до 100 000 000

Все пары дружественных чисел до 100 000 000:

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

(Просчитаны с помощью компьютера на языке программирования C++ за более чем 200 минут работы программы)

Пары дружественных чисел, больших чем 100 000 000:

102023145 116970399

102719740 129063812

103034776 105016424

104887448 105064552

108734050 116251550

109410345 110132055

110960710 125222330

114944072 125269528

115259625 123757335

115447424 118458976

115749344 116983744

116654896 120115664

118458830 131819506

120812175 126671985

121293315 138690045

127924335 148532625

131118975 132926625

131483835 132692805

133089500 176374564

133178325 133471275

133768816 141213584

134312152 139057448

134886465 147382335

136549413 140207067

136770075 155711205

137424188 141993412

138605350 147313850

139009990 156322490

140744835 166562685

140815384 155709416

144788020 186088988

145040288 149364256

146648612 159017308

147366765 182028483

148077644 160128436

и т.д.

Проект BOINC

30 января 2017 года запущен проект распределённых вычислений на платформе BOINC — Amicable Numbers. Поиск дружественных чисел осуществляется как с помощью расчётов на процессоре так и на видеокарте.

См. также

• Обручённые числа
• Совершенное число
• Компанейские числа

Ссылки

• M. García, J. M. Pedersen, H. J. J. te Riele. Amicable pairs, a survey (неопр.) // Report MAS-R0307. — 2003. Архивировано 29 ноября 2006 года. Архивная копия от 29 ноября 2006 на Wayback Machine
• Weisstein, Eric W. Amicable Pair (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Thâbit ibn Kurrah Rule (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Euler's Rule (англ.) на сайте Wolfram MathWorld.
• Amicable Numbers — BOINC проект по поиску дружественных чисел.