Просмотр кода страницы Дружественные числа

'''Дружественные числа''' — пара различных [[натуральное число|натуральных чисел]], для которых сумма всех [[собственный делитель|собственных делителей]] первого числа равна второму числу и наоборот, сумма всех собственных делителей второго числа равна первому числу. То есть, пару натуральных чисел <math>M, N</math> называют дружественной, если:
: <math>m_1 + m_2 + \ldots + m_k = N</math>,
: <math>n_1 + n_2 + \ldots + n_l = M</math>,

где <math>m_1, m_2, \dots m_k</math> — делители числа <math>M</math>, <math>n_1, n_2, \dots n_l</math> — делители числа <math>N</math>.

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

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

Если учитывать все делители, то <math> \sigma(M) - M = N </math> или <math> \sigma(M) = M + N = \sigma(N) </math> — другое определение дружественных чисел, эквивалентное основному. Два числа называются ''дружественной парой'', если они имеют одинаковую сумму всех своих делителей, которая равна сумме этих чисел. Аналогично, три числа образуют дружественную тройку, если они имеют одинаковую сумму всех своих делителей, которая равна сумме этих чисел. <math> \sigma(M) = \sigma(N) = \sigma(K) = M + N + K</math>.

== История ==
Дружественные числа были открыты последователями [[Пифагор]]а; правда, им удалось найти только одну пару дружественных чисел — 220 и 284. Список делителей для 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, — их сумма равна 284; список делителей для 284: 1, 2, 4, 71 и 142, — и сумма равна 220.

Примерно в 850 году арабский астроном и математик [[Ибн Курра, Сабит|Сабит ибн Курра]] предложил формулу{{Переход|#Формула Сабита ибн Курры}} для нахождения некоторых пар дружественных чисел, с её помощью были найдены две новые пары дружественных чисел:
* {{num|17296}} и {{num|18416}};
* {{num|9363584}} и {{num|9437056}}.
В XVIII веке [[Эйлер, Леонард|Эйлер]] нашёл достаточный критерий построения пар дружественных чисел, и в его списке было уже 90 пар. Однако критерий охватывает не все пары: например, пара (1184, 1210) ему не подчиняется, и её обнаружили уже в XIX веке. В XX веке компьютеры помогли найти десятки миллионов пар. Но эффективного общего способа нахождения всех таких пар нет до сих пор.

== Первые пары ==
В [[Онлайн-энциклопедия целочисленных последовательностей|Онлайн-энциклопедии целочисленных последовательностей]] для пар дружественных чисел ведутся несколько последовательностей<ref>{{OEIS|A063990}} — пары дружественных чисел; {{OEIS|A002025}} — меньшие числа в парах; {{OEIS|A002046}} — бо́льшие числа в парах</ref>; отдельно ведётся последовательность сумм чисел в каждой паре<ref>{{OEIS|A180164}}</ref>, примечательно, что все такие суммы, где слагаемые чётны, вплоть до числа <math>1362660800=2^6\cdot5^2\cdot31\cdot83\cdot331</math> (сумма <math>666030256</math> и <math>696630544</math>) [[Делимость|делятся]] на <math>9</math>; также выделена последовательность для дружественных пар, в сумме не делящиеся на <math>9</math><ref>{{OEIS|A291550}}</ref>.

Первые пары:
# {{nums|220|284|x=и|link=yes}} ([[Пифагор]], около 500 до н. э.);
# {{nums|1184|1210|x=и|link=nrl}} (Паганини, [[1866]]);
# {{nums|2620|2924|x=и|link=nrl}} ([[Эйлер, Леонард|Эйлер]], [[1747 год в науке|1747]]);
# {{nums|5020|5564|x=и}} ([[Эйлер, Леонард|Эйлер]], 1747);
# {{nums|6232|6368|x=и}} ([[Эйлер, Леонард|Эйлер]], 1750);
# {{nums|10744|10856|x=и}} ([[Эйлер, Леонард|Эйлер]], 1747);
# {{nums|12285|14595|x=и}} (Браун, 1939);
# {{nums|17296|18416|x=и}} ([[Ибн ал-Банна]], около 1300; [[Ал-Фаризи, Камал ад-Дин|Фариси]], около 1300; [[Ферма, Пьер|Ферма]], 1636);
# {{nums|63020|76084|x=и}} ([[Эйлер, Леонард|Эйлер]], 1747);
# {{nums|66928|66992|x=и}} ([[Эйлер, Леонард|Эйлер]], 1750);
# {{nums|67095|71145|x=и}} ([[Эйлер, Леонард|Эйлер]], 1747);
# {{nums|69615|87633|x=и}} ([[Эйлер, Леонард|Эйлер]], 1747);
# {{nums|79750|88730|x=и}} (Рольф, 1964).

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

=== Формула Сабита ибн Курры ===
Если для натурального числа <math>n>1</math> все три числа:
: <math>p=3\times 2^{n-1}-1</math>,
: <math>q=3\times 2^n-1</math>,
: <math>r=9\times 2^{2n-1}-1</math>,
являются [[простое число|простыми]], то числа <math>2^npq</math> и <math>2^nr</math> образуют пару дружественных чисел.

Эта формула даёт пары (220, 284), ({{num|17296}}, {{num|18416}}) и ({{num|9363584}}, {{num|9437056}}) соответственно для <math>n=2,\;4,\;7</math>, но больше никаких пар дружественных чисел, которые могли бы быть получены по этой формуле для <math>n<20~000</math>, не существует.

=== Формула Эйлера ===
Эйлер расширил формулу ибн Курры — если для натуральных <math>n>m</math> все три числа:
: <math>p=(2^{n-m}+1)\times 2^m-1</math>,
: <math>q=(2^{n-m}+1)\times 2^n-1</math>,
: <math>r=(2^{n-m}+1)^2\times 2^{m+n}-1</math>,

являются [[простое число|простыми]], то числа <math>2^npq</math> и <math>2^nr</math> образуют пару дружественных чисел.
Формула ибн Курры получается из формулы Эйлера подстановкой <math>m=n-1</math>. Формула Эйлера добавила к списку дружественных чисел всего 2 пары: <math>(m,n) = (1,8), (29,40)</math>.

=== Метод Вальтера Боро ===
Если для пары дружественных чисел вида <math>A=au</math> и <math>B=as</math> числа <math>s</math> и <math>p=u+s+1</math> являются простыми, причём <math>a</math> не делится на <math>p</math>, то при всех натуральных <math>n</math>, при которых оба числа <math>q_1=(u+1)p^{n+1}-1</math> и <math>q_2=(u+1)(s+1)p^n-1</math> просты, числа <math>B_1=A p^n q_1</math> и <math>B_2=ap^nq_2</math> — дружественные.

== Открытые проблемы ==
Неизвестно, конечно ли или бесконечно количество пар дружественных чисел. {{На|04|2016|вр=1}} известно более {{num|1000000000|пар}} дружественных чисел<ref>Sergei Chernykh [http://sech.me/ap/ Amicable Pairs list] {{Wayback|url=http://sech.me/ap/ |date=20170816063043 }}</ref>. Все они состоят из чисел одинаковой чётности.

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

Также неизвестно, существуют ли [[взаимно простые числа|взаимно простые]] дружественные числа, но если такая пара дружественных чисел существует, то их произведение должно быть больше {{power|10|67}}.

== Проект BOINC ==
30 января 2017 года запущен проект распределённых вычислений на платформе [[BOINC]] — Amicable Numbers<ref>[https://sech.me/boinc/Amicable/forum_thread.php?id=12 Публичный запуск 30 января 2017]</ref>. Поиск дружественных чисел осуществляется как с помощью расчётов на [[Центральный процессор|процессоре]], так и на [[GPGPU|видеокарте]].

== Примечания ==
{{примечания}}

== Ссылки ==
* {{статья |заглавие=Amicable pairs, a survey |издание=Report MAS-R0307 |ссылка=http://ftp.cwi.nl/CWIreports/MAS/MAS-R0307.pdf |deadlink=yes |archiveurl=https://web.archive.org/web/20061129214421/http://ftp.cwi.nl/CWIreports/MAS/MAS-R0307.pdf |archivedate=2006-11-29 |accessdate=2006-12-17 |язык=und |автор=M. García, J. M. Pedersen, H. J. J. te Riele |год=2003}} {{Wayback|url=http://ftp.cwi.nl/CWIreports/MAS/MAS-R0307.pdf |date=20061129214421 }}
* {{MathWorld |title=Amicable Pair|urlname=AmicablePair}}
* {{MathWorld |title=Thâbit ibn Kurrah Rule|urlname=ThabitibnKurrahRule}}
* {{MathWorld |title=Euler's Rule|urlname=EulersRule}}
* [https://sech.me/boinc/Amicable/ Amicable Numbers ] — проект BOINC по поиску дружественных чисел.


{{Числа по характеристикам делимости}}
{{внешние ссылки}}

[[Категория:Теория чисел]]
[[Категория:Целочисленные последовательности]]