Сумма делителей σ(n)

Давайте найдем сумму делителей числа 360. Для этого можно просто просуммировать все элементы списка делителей.

Plus@@Divisors[360]

Есть и еще один способ. Можно найти сумму первых степеней делителей.

DivisorSigma[1,360]

Пример 8.9. График суммы делителей.

Давайте теперь построим график суммы делителей. Сначала мы используем функции Table и DivisorSigma для построения таблицы tl (точнее, списка) сумм делителей первых n чисел.

t1= TabletDivisorSigma[l,k],{k,l,n=10A3}];

Теперь можем использовать функцию ListPlot для построения графика.

А вот график для n = 100000.

Обратите внимание на то, что все точки графика расположены не ниже прямой у = х, поскольку в сумму делителей включается и само число. Если же само число не включать в сумму делителей, то программа и графики будут несколько иными.

А вот график для n = 100000.

Ниже приведен также график функции у = σ(n)/n.

Интерес представляет также график функции у = σ(n)/(n In n).

Недостаточные, избыточные, совершенные и дружественные числа

Нумерология (или гематрия, как ее еще иногда называют) была распространенным увлечением у древних греков... Делители или аликвотные части играли важную роль в нумерологии.

Поскольку в Древней Греции числа изображались буквами греческого алфавита, каждому написанному слову, каждому имени соответствовало некоторое число. А раз так, можно было сравнивать свойства чисел, соответствующих именам людей, со свойствами (характером) человека. Было сходство или нет, достоверных исторических сведений нет, а вот о свойствах чисел, как мы уже не раз убеждались, есть сведения вполне достоверные, хотя и далеко не полные. Идеальными греки считали совершенные числа, т.е. натуральные числа, равные сумме своих натуральных делителей, меньших самого числа. (Здесь следует отметить, что древние греки не считали само число его делителем.) В некоторой степени это можно понять. Ведь если натуральное число равно сумме своих натуральных делителей, меньших самого числа, то можно сказать, что оно равно сумме своих аликвотных частей. Перенесите это свойство на человека. Получится, что человек с этим свойством как бы самодостаточный, он сможет, подобно Робинзону, преодолеть длительную разлуку с родными, друзьями, сможет преодолеть все стихии. (Ведь такой человек "равен сумме своих частей".) Конечно же, поиску совершенных чисел уделялось огромное внимание. Но мы не станем останавливаться на этом, поскольку, как доказал Эйлер, всякое четное совершенное число имеет вид p = 2^n-1-М_р, где М_p =2^p -1 — простое число Мерсенна. О том, что числа такого вида являются совершенными, писал еще Евклид в IX книге "Начал". Так что каждое простое число Мерсенна порождает четное совершенное число. И, конечно же, наибольший простой делитель каждого четного совершенного числа является простым числом Мерсенна. Так что в некотором роде мы о четных совершенных числах знаем столько же, сколько о простых числах Мерсенна. Что же касается нечетных совершенных чисел, то тут вполне уместен вопрос: а разве совершенные числа бывают нечетными, разве идеал может быть нечетным? Ответ на этот вопрос до сих пор неизвестен. Не попытаться ли найти его с помощью системы Mathematica? Вполне возможно, что система Mathematjca может помочь найти ответ и на этот вопрос. Но пока лобовой атакой, даже при поддержке системы Mathematica, крепости Нечетных Совершенных Чисел не удастся не только взять, но и даже дойти до нее. Ведь как показал автор одного из лучших учебников классической теории чисел Александр Адольфович Бухштаб, наименьшее нечетное совершенное число, если оно существует, имеет не менее двух с половиной тысяч цифр (в десятичной системе счисления). Для прямого перебора всех нечетных чисел это слишком много. Впрочем, всегда были смельчаки, которые пытались перебирать нечетные числа, используя те или иные дополнительные ухищрения. Еще в 1968 году Брайен Такерман из IBM подобрался, например, к 36-значным числам. К 1977 году всевозможные ухищрения позволили отбраковать все числа до 1050. Если нечетные простые числа существуют, то они имеют не менее 2800 различных простых множителей и имеют вид p^4t+1 N₂, где р — простое число вида 4_n+l, a # взаимно просто с р. Давайте же уточним нижнюю оценку количества цифр в наименьшем нечетном совершенном числе. Как только что было сказано, такое число содержит не менее 2800 различных простых множителей, причем все они, кроме, возможно, одного, входят в степени не ниже 1. Поскольку рассматриваемое число нечетное, то 2 среди этих простых чисел отсутствует. Значит, чтобы получить нижнюю границу, мы можем возвести в квадрат произведение 2800 простых чисел рr = 3, Р3 = 5, ..., рrm = 25409 и разделить ее на наибольшее число в этом произведении, т.е. на р[n] = 25409. С системой Mathematica нет проблем.

Конец я опустил, потому что в полученном результате 21 892 цифры.

IntegerPart[Log[10,nn]]

.21891

Это результат, которого еще никому не удалось достигнуть! Хотя вычисленное нами число имеет вид р4М -N2, оно не совершенное, так как сумма всех его делителей, не считая самого числа, является числом, имеющим 21 893 цифры.

IntegerPart[Log[10,DivisorSigma[l,nn]-nn]]

Значит, сумма всех делителей этого числа, не считая самого числа, больше самого числа. Число, сумма всех делителей которого, не считая самого числа, больше самого числа, называется избыточным. Иными словами, число п называется избыточным, если о(n)>2n. Честно говоря, несколько удивительно то, что это число оказалось избыточным. Сейчас объясню, почему. Давайте найдем все избыточные нечетные числа, меньшие 100 000. Вот нужная нам программа.

Как видите, первым нечетным избыточным числом является 945. А избыточных нечетных чисел, меньших 100 000, всего 210. Это очень мало! Так что нам очень повезло: первое встреченное нами число оказалось избыточным нечетным. Остальные нечетные числа, меньшие 100 000, являются недостаточными. (Число, сумма всех делителей которого, не' считая самого числа, меньше самого числа, называется недостаточным. Иными словами, число л называется недостаточным, если о(n)<2и.) Как много бедных, как мало богатых... Ох, простите, я хотел сказать как много чисел недостаточных, как мало избыточных среди нечетных чисел, меньших 100 000. Если через А(х) обозначить число избыточных чисел, меньших или равных х, то 0,1241х<^(х)<0,314х, так что большинство чисел является недостаточным. Хотя существование предела отношения

А может ли последовательность х0 = a, n, = σ(n)-n, ..., x_n+1 = σ(x_n)-nr1, ... иметь период? Ведь если бы такое случилось, то, с точки зрения древних греков, этот период был бы "самодостаточным"! Известны случаи, когда эта последовательность вообще постоянна. Конечно, это происходит в том случае, если л — совершенное число. Но совершенных чисел так мало, а опасных, дальних дорог (хотя бы за золотым руном) так много! На все дороги не напастись совершенных чисел. Может быть, в такие дальние путешествия можно отправлять не только совершенные числа, но и периоды из таких последовательностей? С точки зрения древних греков, думаю, неплохая идея. Но длинные периоды — многочисленные экипажи. А для многочисленных экипажей нужны очень большие суда. Другое дело постоянные последовательности. У постоянных последовательностей длина периода равна 1. Но эти последовательности встречаются, как мы знаем, весьма редко. (Только отчаянные смельчаки могут рискнуть отправиться в дальнее одиночное плавание.) К тому же неизвестно, бесконечно ли их число. Затем идут последовательности, у которых длина периода равна 2. Есть ли такие? Период таких последовательностей состоит всего из двух чисел, таких, что сумма делителей одного числа равна другому (напомним, что сами числа при подсчете суммы не учитываются). Фактически такой период является идеальной "супружеской" парой, в которой недостаток "чувств" (слагаемых) одного "супруга" (числа) компенсируется избытком "чувств" (слагаемых) другого. Такие пары чисел называются дружественными. Иными словами, пара (а, b) различных натуральных чисел афЬ называется дружественной, если о(n)—а = b, a a(b)—b — а. Увы, грекам не повезло: они знали лишь одну дружественную пару: 220 и 284. Лишь в 1636 году (письмо Мерсенну датировано 24 июня) Пьеру Ферма удалось найти еще одну: (17296, 18418). А сколько сможем найти мы? С помощью системы Mathematica, разумеется. Попробуем. Сначала определим функцию, определяющую, есть ли у избыточного числа а недостаточный "супруг". Заметьте, что избыточное число всегда меньше своего недостаточного "супруга". Вот нужная нам функция.

Friend[n_]:=Module[ft},

If[(t=DivisorSigma[1,n]-n)>n,

If[DivisorSigma[1,t]-t==n,t,0],0]]

Эта функция находит большего (значит, недостаточного) "супруга", если он есть, и "рекомендует" число 0, если большего "супруга" нет. Осталось определить, что мы будем печатать, и запустить перебор. Давайте печатать номер найденной пары, ее избыточное (меньшее) число, его каноническое разложение, а затем недостаточное (большее) число и его каноническое разложение.

prn:=Print[n,":",а,":",FactorInteger[a],":",b,":",

FactorInteger[b]]

Запускаем перебор.

For[n=0;а=1,а<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-2^n-1-1, q= 3-2ⁿ-1 и r-=9-22^n-1-1 — простые, то числа А- M *p-q и 5 = Т *rr — дружественные.

При n = 2 получается пара чисел, найденная Пифагором. Однако теорема Сабита дает дружественные числа и при других п, например при n = 4 и n = 7. С помощью "вульгарного" применения ЭВМ блюстители чистоты спортивных традиций обнаружили, что этими тремя случаями исчерпываются все значения и<20 000, при которых все три числа р = 3-2^n-1—1, q= 3-2ⁿ-1 и r= 9*2^2n-1-1 — простые. Иными словами, для и<20 000 указанный способ дает дружественные числа только при n = 2, n = 4 и n = 7. Использовал ли сам Сабит свою теорему для отыскания дружественных чисел при я>2, неизвестно. Открытие второй (n = 4) и третьей (n = 7) пар дружественных чисел приписывалось ранее Ферма и Декарту соответственно. Однако в одном из трактатов марокканского ученого ибн аль-Банны (1256—1321), сына архитектора, были обнаружены следующие строки: "Числа 17296 и 18416 являются дружественными; одно из них избыточно, другое недостаточно. Аллах всеведущ".

С течением времени формулы, предложенные Сабитом, были забыты, а его книгу открыли заново лишь в XIX веке. Впрочем, многие античные и арабские ученые, а также ученые средневековья посвящали в своих трактатах одну из глав совершенным и дружественным числам. Однако большей частью в этих трактатах было мало новых сведений и много ошибок. Правда, очень удивляет то поразительное единодушие, с которым авторы этих сочинений настаивают на возможности практического использования дружественных чисел. Например, ибн Хальдун прилагает к своему трактату руководство по изготовлению талисмана дружбы, а мадридский ученый аль-Маджрити (ум. в 1007 г.) приводит рецепт, позволяющий добиться взаимности в любви: надо записать на чем-либо числа 220 и 284, меньшее дать съесть предмету страсти, а большее съесть самому; ученый добавляет, что действенность этого способа он проверил на себе.

Пьер Ферма в 1636 году и Ренэ Декарт в 1638 году независимо друг от друга вновь открыли формулы Сабита. О датах и обстоятельствах этих открытий имеются самые точные сведения, потому что Ферма и Декарт написали Мерсенну, который в предисловии к своей ближайшей книге (Les nouvelles pensees de Galilee (1639)) назвал их открытие крупным достижением гениальных математиков. (Между прочим, в ходе своих исследований Ферма и Декарт вывели формулу, дающую сумму делителей числа по его представлению в виде произведения степеней простых чисел. Можно ли сомневаться, что Мерсенн ее знал?)

Так вот, Вальтер Боро, один из тех весьма удачливых рыбаков, что сознались в том, что просили других вычислителей (Херман те Риле был наиболее удачливым из них) посчитать кое-что на ЭВМ, придумал вот что. Раз способ Сабита дает столь мало дружественных пар, значит, нужно придумать целую серию таких правил. С этой целью он придумал свой рецепт.

Рецепт Вальтера Боро. Если для пары дружественных чисел вида А= а^-nи В = a-s числа s и р = n + s+l являются простыми, причем а не делится на р, то при всех тех натуральных и, при которых оба числа qt = (n + 1)рⁿ+> -1 и nr= (u + l)(s + 1)р"-I просты,числа В1 = N//</, и В^r = apⁿ*q2 —дружественные.

Рассмотрим пример применения правила. Возьмем пару Пифагора: А = 220 = 22-55 и 5= 284= 22-71. Положим а = 22, и = 55, s =71.

Числа s = 71 и р = n + s+ 1 = 55 + 72 = 127 — простые. Поэтому можно использовать указанное правило. При n= 1 числа <?, = (м + 1)р"+1-1 и <?2 = (u + l)(s + l)pa_-1 не являются простыми, но уже при n = 2 мы получаем пару дружественных чисел В, = 220-1272-903223, В, = 4-1272-65032127.

Эти довольно большие числа, полученные из пары (220, 284) почти без всяких вычислений, не были известны до открытия "рецепта"!

Еще один пример. Возьмем пару Эйлера А = З4*5 * 11 * 29* 89 = а *n и В= 3ⁿ-5-11-2699 = a*s.

Здесь также числа s = 2699 up=u + s+l = 5281 являются простыми. Таким образом, по этой паре Эйлера тоже можно построить соответствующее "правило Сабита-Боро". В этом случае уже при a= 1 числа <?, = (n + 1)M^n-1-1 и q2 = (u + l)(s + l)p^a-1 будут простыми, и мы получаем дружественные числа

В1 = 34-5-11-29-89-5281-13635541,

В2 = 34-5-11-5281- 36815963399.

Рецепт работает! Но как его нашел Вальтер Боро? Он решил искать дружественные пары, в которых оба числа имеют вид Bl-b1-pⁿ-q1 с простыми р, q, и <?, (1= 1, 2). Иными словами, выбираются и фиксируются три числа B1, B2,р,и при каждом n - 1, 2, 3, ... ищутся N и N_r. Поскольку В1 и В2 — дружественные числа, то а( В,) = В, + В2 = о( В2), откуда следует, что

Теперь, вспоминая, что сумма делителей мультипликативна, т.е. а(ху) = а(х)а(у) для взаимно простых х и у, причем

(р — простое), получим:

Замечаем, что при n числа n и M, также стремятся к бесконечности. Таким образом, переходя в последнем равенстве к пределу при n->-1, получаем основное уравнение

Это соотношение связывает три числа q1,q2 и p, которые следует подставлять в исходную формулу B_i=b_i*pⁿ*q_i. Отыскивая простейшие решения основного уравнения

₁= 220, B2= 4и из основного уравнения найдем для р значение 127. Тем самым мы получим ранее наиденную пару B1=220.127² 903223 и B2=4*127² *65032127 .

Правда, вначале одно из больших чисел ,, и ь все время оказывалось составным. Но второго октября 1972 года Херман те Риле сообшил, что по Формуле приведенной в качестве примера для пары Эйлера А - 3 -5.11-29-89 -а ы и 5 =34-5-11-2699 = а-5, при я = 19 получаются числа 9|=(« + 1)Р 1 и а -(« + 1)(,+1)/-1 по меньшей мере псевдопростые (под псевдопростьш числом здес2ь подразумевается такое число ,. для которого выполняется сравнение малой теоремы Ферма.

Число А имеет 800 различных делителей, а число В — 3200.

DivisorSigma[О,А]

DivisorSigma[О,В]

Простым перебором эту пару, конечно, не найти. Система Mathematica позволяет в мгновение ока найти канонические разложения чисел этой пары.

Ну, теперь хоть можете узнать те сомножители, которые эта пара "заимствовала" у пары Эйлера? Без системы Mathematica их бы без усилий не найти!

Содержание раздела