Недостаточные, избыточные, совершенные и дружественные числа
Сначала определим функцию, определяющую, есть ли у избыточного числа а недостаточный "супруг". Заметьте, что избыточное число всегда меньше своего недостаточного "супруга". Вот нужная нам функция.
Friend[n_] := Module[ft}, If[(t=DivisorSigma[1,n]-n)>n, If[DivisorSigma[1,t]-t==n,t,0],0]]Эта функция находит большего (значит, недостаточного) "супруга", если он есть, и "рекомендует" число 0, если большего "супруга" нет. Осталось определить, что мы будем печатать, и запустить перебор. Давайте печатать номер найденной пары, ее избыточное (меньшее) число, его каноническое разложение, а затем недостаточное (большее) число и его каноническое разложение.
prn := Print[n,":",a,":",FactorInteger[a],":",b,":", FactorInteger[b]]Запускаем перебор.
For[n=0;a=1,a<10^7,a++,If[(b=Friend[a])>0,n++;prn]]Результаты перебора оформляем в виде таблицы.
Как видно из таблицы, в пределах первой тысячи есть только одна дружественная пара (220, 284) – та, которую знал еще Пифагор! В пределах первых десяти тысяч есть всего лишь 5 дружественных пар, а в пределах первых ста тысяч их только 13. Не удивительно, что поиск, дружественных чисел напоминал охоту за редкой дичью. Недостижимым чемпионом долгое время был Эйлер. Его рекорд побил бельгиец Поль Пуле, который в Брюсселе в 1929 году издал двухтомную монографию по теории чисел под многозначительным названием "La chasse aux nombres" ("Охота за числами"). Кроме всего прочего, в ней приведены 62 новые пары дружественных чисел. Пуле (как ранее Лежандр и Чебышев) пошел по пути открытия новых критериев простоты чисел. Значительная часть его исследований посвящена развитию идей французского математика Люка, открывшего в высшей степени эффективные критерии простоты.
Новый "мировой рекорд" установил американец Э. Эскотт, а затем рекорд перешел к его соотечественнику Элвину Дж. Ли. По существу, они также пользовались методами Эйлера, хотя и в усовершенствованной форме. Правда, Ли нарушил правила спортивного соревнования – он был первым, кто прибегнул в столь больших масштабах к помощи ЭВМ. Зато он нашел 390 дружественных пар! Весьма любопытна таблица "чемпионата".
Наконец, использованный нами метод перебора был применен в Йельском университете на IBM 7094, – там были проверены все числа до миллиона, и было обнаружено, что в пределах миллиона имеется всего 42 дружественные пары. При этом были найдены (в небольшом количестве, правда) ранее неизвестные пары.
С наступлением эры ЭВМ появилась новая возможность, о которой Эйлер не мог и помышлять, – заставить машину перебирать все числа подряд, пока хватит машинного времени. Конечно, нашлись люди, которые только и ждали, когда появится возможность производить громадные вычисления. Они занимались ими в течение двух лет, не считаясь с затратами, и добрались до десятизначных чисел. (По некоторым сведениям еще до 1968 году путем перебора с некоторыми ухищрениями поиски пар дружественных чисел разной четности были проведены до трех миллиардов, но результатов не дали.) Некоторые квалифицировали это как грубый нажим конкурентов на таких тонких и искусных ловцов чисел, какими были Эйлер, Пуле и Ли. Как к этому относиться? Блюстители "чистоты" спортивных соревнований даже сравнивают тонких и искусных ловцов со страстными рыболовами-любителями, неожиданно замечающими у ручья людей, которые просто осушают русло и затем спокойно собирают рыбу! Впрочем, при этом обнаружилось, что рыболовы удили весьма успешно и выловили почти всю рыбу, так что "браконьерам" досталась лишь довольно скромная добыча. Впрочем, те из блюстителей чистоты спортивных традиций, которые сами были успешными рыболовами, сознались, что они тоже… Нет, упаси Боже, они не подходили к пульту ЭВМ, они просто просили (я бы сказал истошно взывали) других людей найти простые числа в довольно длинной последовательности чисел определенного вида…
Как же получилось так, что дружественные пары открывались не последовательно, а "вразброс"? Почему после пары Пифагора (220, 284) Пьер Ферма нашел пару (17296, 18418), пропустив, как видно из нашей таблицы, сразу 6 пар? Оказывается, Пьер Ферма (и Ренэ Декарт) открыли способ получения дружественных чисел (правило), который знал арабский математик, врач и астроном Сабит (тот самый абу-Хасан Сабит ибн Корра ибн Марван аль-Харани) еще в IX веке. Этот способ получения дружественных чисел звучит на современном языке так.
Теорема Сабита.
Если все три числа р= 3-2n-1 -1, q= 3-2n -1 и r-=9-22n-1 -1 – простые, то числа А – M *p-q и 5 = Т *rr – дружественные.
При n = 2 получается пара чисел, найденная Пифагором. Однако теорема Сабита дает дружественные числа и при других п, например при n = 4 и n = 7. С помощью "вульгарного" применения ЭВМ блюстители чистоты спортивных традиций обнаружили, что этими тремя случаями исчерпываются все значения и<20 000, при которых все три числа р = 3-2n-1 -1, q= 3-2n -1 и r= 9*22n-1 -1 – простые. Иными словами, для и<20 000 указанный способ дает дружественные числа только при n = 2, n = 4 и n = 7. Использовал ли сам Сабит свою теорему для отыскания дружественных чисел при я>2, неизвестно. Открытие второй (n = 4) и третьей (n = 7) пар дружественных чисел приписывалось ранее Ферма и Декарту соответственно. Однако в одном из трактатов марокканского ученого ибн аль-Банны (1256-1321), сына архитектора, были обнаружены следующие строки: "Числа 17296 и 18416 являются дружественными; одно из них избыточно, другое недостаточно. Аллах всеведущ".