книги / Mathematica 5. ╨б╨░╨╝╨╛╤Г╤З╨╕╤В╨╡╨╗╤М

функция Кармайкла Х(т) — CarmichaelLambda

Если а и т взаимно простые, то аф(т) = l(modw). Но всегда ли <р(/и) является наи­

меньшим натуральным числом с таким свойством? Оказывается, нет. Например, для модуля 8 имеем следующую приведенную систему вычетов.

s=Select[Range[8],GCD[#, 8]==1&]

{ 1 , 3 , 5 , 7 }

Квадраты этих вычетов сравнимы с 1 по модулю 8.

Mod [ %Л2,8 ]

{1,1,1г1)

Однако

EulerPhi [8] 4

Так что <р(8) не является наименьшим натуральным числом, удовлетворяющим сравнению ах =l(mod8) для всех а, взаимно простых с 8.

Значения, меньшие <р(/я), иногда доставляет обобщенная функция Эйлера Цт). Вдвое меньшие значения для модулей, кратных 8, дает функция Люка /(/и). А наи­

меньшее натуральное число, удовлетворяющее сравнению ах = l(modm) для всех а,

взаимно простых с т, обозначается Х(т). Функция X называется функцией Кармайкла. |Всистеме Mathematica у нее имя CarmichaelLambda.

| Вот как можно вывести те натуральные числа, для которых Х(т)<у(т).

Do[If[EulerPhi [n] != CarmichaelLambda [n] , Print[n,":",EulerPhi[n], " : CarmichaelLambda[n]]],{n,k=100}]

Выполните эту программу, и вы увидите, что их довольно много.

Пример 8.3. График функции Кармайкла.

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

tl= Table [CarmichaelLambda [k] ,{k, 1,n=10A3}];

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

ListPlot [tl,PlotRange->All]

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

20000 40000 60000 80000 100000

Сравните,эти графики с графиками функции Эйлера. Сразу видно, что лучи на графике функции Кармайкла прижимаются к оси абсцисс гораздо ближе, чем на гра­ фике функции Эйлера.

Функция Мебиуса |i(m) — MoebiusMu

Функция Мебиуса ц(т) = 1, если т есть произведение четного числа различных простых чисел; ц(/я) = —1, если т есть произведение нечетного числа различных про­ стых чисел; |i(m) = 0, если т делится на квадрат какого-либо простого числа. Вот как вычисляется эта функция.

MoebiusMu[210]

1

Пример 8.4. График функции Мебиуса.

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

tl= Table [MoebiusMu [k] ,{k, 1,п=10л3} ];

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

функции, связанные с делителями, — Divisors и DivisorSigma

При необходимости нужно указать опцию G a u ssia n In te g e rs -> T ru e . Без этой опции делители натуральных чисел находятся только среди натуральных чисел.

Divisors [320]

( 1 , 2 , 4 , 5 , 8, 1 0 , 1 6 , 2 0 , 3 2 , 4 0 , 6 4 , 8 0 , 160, 320}

Если же указать эту опцию, то даже у натурального числа будут найдены все его

Есть несколько важных числовых функций, связанных с делителями. Прежде всего это сумма к-х степеней всех делителей данного числа. Эта функция часто обозначает­ сятак: с к(п) . При к = 0 получаем количество делителей т(л), а при к = 1 — сумму де­

лителей о(л). (В принципе совсем несложно получить и значения основных симмет­ рических многочленов от делителей, а значит, и составить алгебраическое уравнение, корнями которого являются делители заданного числа.) В системе Mathematica эта функция называется DivisorSigma [к, п].

Число д е л и т е л е й Т (л)

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

LengthQDivisors [360]

24

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

DivisorSigma [0, 360]

24

Числа с заданным числом делителей

Существует единственное натуральное число п = 1, которое имеет только один дели­

(m, + l) (/м2+1) (mk +1) = 3. Поскольку 3 — простое число, то слева только один множитель может быть отличен от 1. Поэтому к = 1, а /л, = 2. Поэтому ровно 3 дели­

теля имеют квадраты простых чисел, и только они. Наименьшим числом с 3 делителями является, конечно, 4.

Так же легко найти и все числа, имеющие простое число делителей. Обозначим число делителей через q: т(п) = q. Тогда (/и, + 1) (/и, +1) (тк +1) = q. Поскольку q - простое число, то слева только один множитель может быть отличен от 1. Поэтому к = 1, а ш, = q — 1. Поэтому простое число делителей имеют степени простых чисел, и только в том случае, если показатель степени на 1 меньше простого числа. Наименьшим

изведения квадратов простых чисел на другое простое число. Наименьшим числом с 6 де­ лителями является, конечно, 12.

В принципе этот метод можно использовать для вычисления наименьших нату­ ральных чисел, имеющих заданное число делителей.

Впрочем, иногда легче отыскать такое число в таблице, указывающей количество делителей для различных чисел. Составить такую таблицу с помощью системы Mathcmatica не составляет труда.

DotPrint[п,":",DivisorSigma[0,п]],{ п , к=50}]

Но едва ли стоит иметь такую таблицу в напечатанном виде. Ведь в компьютерную эпоху поиск путем визуального просмотра нескольких сот страниц справедливо счита­ ется не наиболее легким решением. Проще модифицировать программу.

Пример 8.5. Наименьшее число, имеющее 14 делителей. Предположим, нужно найти наименьшее число, имеющее 14 делителей. Тогда программу можно модифициро­ вать так.

While!!DivisorSigma[0*n] !=m,n++];

Prints, "i",DivisorSigma[0#n] ]

Выполнив эту программу, получим результат.

192 14

Пример 8*6» Наименьшее число, имеющее 100 делителей. Предположим, нужно най­ ти наименьшее число, имеющее 100 делителей. Тогда нужно выполнить следующую программу.

ro~l©(QU

m~l;

While IlDivisorSig®afOtn] !*m,n++]; Println* ":%Oivis©rSigmalO*n]1

Выполнив эту программу, получим результат.

4536(0 100

Честно говоря, здесь было немного риска. Ведь если бы числа с заданным числом делителей не оказалось, программа бы зациклилась. Но фокус в том, что всегда суще­ ствует число, имеющее любое (натуральное, конечно) наперед заданное количество делителей.

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

Итак, пусть число делителей равно г s, где г и s — простые числа. Тогда п = р п~х

или п = p r~lq s~l, где р и q — произвольные простые числа.

Но, тем не менее, иногда программа, подобная приведенным выше, работает слишком долго. С ее помощью не удастся, например, за приемлемое время найти наименьшее число, имеющее миллион делителей.

Пример 8.7. Наименьшее число, имеющее миллион делителей. Известный немецкий популяризатор математики Вальтер Литцман в середине XX столетия писал, что со­ гласно математическому бюллетеню Буэнос-Айреса в работе Мерсенна Cogitaeta physico-matematica, изданной в Париже в 1644 году, было указано, что наименьшее число, имеющее миллион делителей, есть

п = 126765060022822940149670320537666 • 8472886094434

Однако Вальтер Литцман заметил, что некоторые усомнились в этом и послали вопрос в Bolletino di M atem atica (4-я серия, т. II, с. 28), было ли доказано это утвер­ ждение. Опять же, как сообщает Вальтер Литцман, ответ не был получен.

Давайте хотя бы частично проверим утверждение, сделанное в математическом бюллетене Буэнос-Айреса. Конечно, система Mathematica не может нам помочь про­ верить, действительно ли Мерсенн, а не кто-то другой нашел это число. Точно так же она не может нам помочь проверить, действительно ли в 1644 году, а не в каком-то другом было сделано это сообщение. Но зато система Mathematica может помочь при подсчете делителей этого числа.

nl=1267650 60022822 94014 9670320537 6; п2=п1л66; п3=847288609443; п4=пЗА4; п5=п2*п4;

D ivisorS igm a [0 , п5]

666701

Как видите, миллионом здесь и не пахнет! Так что сомнения были не напрасными. Но опять же Вальтер Литцман указывает, что это число является 2028-значным. Это легко проверить.

п5

3236658312601158337142676859591718919531912249395991685576106473408423

6031639529115022573790648494491788198338845883966201037519721015370165

4784312808668771766093896828358572192892957860010973568038220423714357

2158984940035586508582869648355172467374624210888626387457073359624138

2596489915025596066368968538815513398780409013543964734833007423408416

0412374262867575264854040632926903224197206374423543990785154576078631

0968815453807177282327607607949333295941187510812162003239728076457949

3824516711012734712907551213905399195367369225154908798452884960136925

6023409517195045519535221804719390205943100351132833534761468789312929

9861825287926873313138854560029982271650686632885840714138093236383588

0799210382128771765867807432661377765323101167177441273789741762077976

5533981505244889662194966793585259321807220026241819596576733764642642

3333930765289139679693982062282029119751071670885825726506116957246585 :0401928384369784686599033050087 80637895728293612361594846004 6839510135 2315010188425643616533003514643759281762684708676986009208844862356419

5078960666636678656966528600694213951464823318742697634976731726906003

0877463437298705485121346456074886231298773001008644536250815150337003

9065694703468749381150975831726011660009586064203636554405931200864033

2443300387462290221920718821768068798605468996733985186116897867104433

0996371223609859885977237101233421485113195915044917112726320927028668

8111091180327547133931346298011087994017938839442171047248971689323381

3046960875297765438588390438510993481109414691549867066197732127186772

5197355548538386239159116501699604886482484966030905757691263674419326

6070012301630349073175087899003022634768639332680673399964853717619093

0170745836949950850949997421383235702267223072666184825152791115026054

5390639154830375448223316018279417475397173407499357600486758019286952

6643548990909323149801282675045307459437397597214359060767738721376063

5503171356697263274200791008819314211728666486254636610835083566045391

8011737700746337040667662108370074741555251691026236596733909598922877

17376

Как бы не так! Тут аж 2035 цифр! Возможно, где-то прокралась опечатка. Но где? Вальтер Литцман указывает также, что число nl имеет 100 делителей. Проверим это.

DivisorSigma[0,nl]

101

Не волнуйтесь, с числом nl все в порядке. Вальтер Литцман по традиции, восхо­ дящей к древним грекам, не учитывает при подсчете делителей само число. В отсутст­ вии опечатки в числе легко убедиться.

Factorlnteger[nl]

[{2,100}}

Да это же сотая степень двойки! А что за зверь является основанием второго со­ множителя? Не степень ли числа 3? Проверяем.

Factorlnteger[пЗ]

[{3,25}}

Так и есть! Теперь мы можем предположить, что Мерсенн указал число вида 2' • Зу Чтобы найти х н у , достаточно решить уравнение (х+1)(у+1)-1 = 1000000 в на­ туральных числах. Приведем это уравнение к виду (х+1)(у+1) = 1000001. Найдем ка­ ноническое разложение числа 1000001.

Factorlnteger[1000001]

у = 100. Как видим, вариантов не много. Все зависит от того, какое число мень­ ше: 29900• З100 или 2100-39Х0. Конечно, 29900-3|00<2|00-39900. Это очевидно, и тут Мерсенн ошибиться не мог. Так что х = 9900 и у — 100. Но это значит, что найденное Мерсенном число можно записать так: 2”00-3'00 = (г100)99 ^ 25)4 Так что опечатка, оказывается, в

показателе степени: вместо 99 там указано 66. Если учесть технологию верстки книг до середины прошлого столетия (текст приходилось набирать в “перевернутом” виде), то нужно признать, что цифры 6 и 9 можно было запросто перепутать. Поэтому такая ошибка вполне вероятна. Давайте теперь проверим, что мы не ошиблись и найденное нами число действительно имеет миллион (не считая самого себя) делителей.

nl=126765060022822940149670320537б;

n2=nlA99;

п3=847288609443;

п4=пЗА4;

n5=n2*n4;

DivisorSigma[0,n5]

1000001

Сошлось, как в аптеке! Но беспокоит вот что: найденное нами число больше того, которое было указано Вальтером Литцманом. А указанное им число имело 2035 зна­ ков, хотя он указал, что должно быть всего лишь 2048 цифр. Давайте посмотрим, ка­ кое число получилось у нас.

п5

8111152100561178773348451131826314779581764341047505731099235868919825

5442480571530880988505397727910307628411880633048886499261609446929489

3867713937778644428517049201189447456208150645898211095461922298156925

6304762220308664799761408366387128642970664616480193635522675895842590

9565885262558643138961577116800487105440172112346291819392355832711740

1695109623723828170221816802532116456537410582890232937928325084148601

4269716730622162790815457819610992704737577546104972827473106560276688

5966167064492110263340438420456755683719440166323230166343714670115564

9683570567829128018748630798086550981982970224056730513417847877178541

5923876872358452685243867917787858446387083193320939747549064452441070

0211240644994469117355168461029660579705262861576541222900072926943596

3282065079614530445095346188187258144756291159308614864662331803857059

1207303941942371564399843180016281747072662405210452830604403392891216

3450680128755320313895357983303274181046523852923319870964231962530208

5610951277303902557570881939863121015289578382145434238115446003310248

0594699854024210636322349616611755512474154987171947097088326334148182

0222857428411,82010^148109898294459575724839809247954128396828396345742

4420275306707009174470489511271736529886782096131874087710367023221794

7218724045840132215685132363013713541775078323498686004208045179533605

2348632337106115560340100576886258342489103044740037186650023745278435

235998070778701425358773667573765909550739719381717867341972.2101336055

8939988883991600013357678463931445771558541053909430022696045798816363

3290922767269195605415443020160137451865259735706455139586733224828065

3240241472706357835231041022453069870134907996749789110106610043752637

3297510415991881137470465766402364243707641164582593272806426641073015

4424333531792555292530585400365238984278702765501250948720443527603018 05О3569268419768617Ю1311'6314 9126454 6677501239687473616221467674231485 1590775540935425859899409155323963522188395050660458044849295322662436 4252653936957303048310914840731093572720876202707725001403020106722895 9073170222003525414588878497771135429471599683047126051868550712314159 5323878271591788141650880963602706147542113714009948252146870022588753 4224667007640058605997041812248340446181716744667464291891086601140338 4937618966754845673033255979377304933306920530676381421564672608189201 6576728088966994609723936643350833819339883390503355560378970814070732 1206993922370976820393538677531682790630314029322126838221367213429408 9661891952971072080897356697814838127321467449269963260227051376120109 6862383521011735448636930522585863378592031125905804002940398407544003 1512506517145598711531815598892375099034903242075524392130773661057828 2679636031364703919640203709134989068132205150916979551422171972127658 6211963394976973807223359010390417069410217329671266483333928585202749 3132279852448908489700429509061988981399352881208573405544826913981018 0290740680131866924231270872798371504392526878153870726862505266109446 6649467944702608363950185804311335945452067105655953888610714167998672 432085216710885376

Это число имеет 3028 цифр! Ага, опять опечатка! А вдруг нет? Ведь мы еще не проверили, что найденное нами число наименьшее.

Пусть л = — каноническое разложение искомого числа, причем в

этом разложении простые числа записаны в порядке возрастания. Тогда т(л) = (m,+1)

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

тивном случае мы могли бы уменьшить число, переставив показатели /и,, т , , ..., тк,

что совершенно не повлияло бы на количество делителей.) Далее, поскольку (т,+1)х

х(ш2 +1) (/л*+1) = 101x9901 и все множители в правой части простые, к<2. Если

к — 2, то р х = 2, р, = 3; все возможные варианты в этом случае мы только что ис­

следовали. Если же к = 1, то р, = 2, но зато т, = 1000000. Других вариантов в этом

случае нет. Но 2,(ШЮ0 имеет 301030 цифр.

IntegerPart[Log[ГО,2Л1000000] ]

301029

Так что 2,0(ШЮ> 29900 • З100 Итак, мы доказали, что наименьшим числом, имеющим

миллион (не считая самого числа) делителей, является 29900 -3100 , имеющее 3048 цифр. Как видите, с помощью системы Mathematica мы провели полное исследование математической части сообщения, сделанного Вальтером Литцманом. Что же касается расследования по исторической части сообщения, то здесь я не могу похвастаться особыми успехами. Дело в том, как научный сотрудник, не связанный со спецслуж­ бами, я не смог получить доступ к оригиналам работ Вальтера Литцмана. (Если вы не связаны с этими самыми спецслужбами, то вы хорошо знаете, что сотрудники “самой научной” библиотеки всегда найдут повод отказать вам в выдаче книги, которая, как кажется сотрудникам этих самых служб, может “недостаточно активно” восхвалять существующий строй. А тут зарубежные книги. Тем более популярные. Кто знает, что они там популяризируют?) Поэтому я видел работы Вальтера Литцмана только в пе­ реводе. Мне самому приходилось переводить различные книги, и я хорошо знаю, на­ сколько пренебрежительно в некоторых издательствах относятся к словам автора. Особенно в советских. Там больше смотрели как бы чего не вышло, а далеко не за точностью передачи мысли автора и не за отсутствием опечаток в листингах. Опечат­ ки в вышеупомянутом сообщении я обнаружил еще тогда, когда конструировал сис­ темы компьютерной алгебры. Но эти опечатки, конечно, я обнаружил в переводе. Вполне вероятно, что они были сделаны при печати перевода. Но ведь если бы в ма­ тематическом бюллетене Буэнос-Айреса все было напечатано без опечаток, то почему в Boltetino d i M atematica был направлен вопрос? В чем было сомнение? В математиче­ ских способностях Мерсенна? В энциклопедии Britannica сказано, что Мерсенн дей­ ствительно публиковал работу Cogiiaeta physico-m atem atica и издана она была в Париже в 1644 году. Там же сказано, что он был хорошо знаком с работами Ренэ Декарта, Блеза Паскаля, Галилео Галилея, Христиана Гюйгенса, Пьера Ферма... В 1635 году он основал (частную) Парижскую Академию Наук (Academie Parisienne), которая затем стала Академией Наук Франции... В чем, собственно, было сомнение? В том, что Мерсенн смог найти разложение 1000001 = 101x9901? При его-то энергии? В том, что

Мерсенн знал формулу для числа делителей т(л) = (m ,+1) (m2+ 1) (/п4+1)? Едва

ли, без нее даже подсчитать число делителей было бы весьма трудно. Да и формулу для суммы делителей, очень похожую на формулу для количества делителей, вывели Пьер Ферма и Ренэ Декарт. Причем своими изысканиями в области дружественных чисел Пьер Ферма и Ренэ Декарт занимались независимо, хотя и пришли к тем же формулам, что и один из самых выдающихся арабских математиков абу-Хасан Сабит ибн Корра ибн Марван аль-Харани (836-901). Пьер Ферма сообщил Мерсенну о сво­ ем открытии правила Сабита в 1636 году (письмо Мерсенну датировано 24 июня), а Ренэ Декарт — в 1638 году (письмо Мерсенну датировано 31 марта), т.е. за 8 и 6 лет до выхода работы Мерсенна Cogitaeta physico-m atem atica. Так что наиболее вероятным мне кажется, что опечатки все же были не только в переводах или в работах Вальтера Литцмана... Если вспомнить, что в средние века в книгах слова печатались подряд, без пробелов, а математическая символика практически отсутствовала, то вполне ве­ роятной выглядит версия об опечатке в показателе степени...

Пример 8.8. График количества делителей.

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

делителей первых п чисел.

tl= Table [DivisorSigma [0,k],{k,1,п=10л3}];

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

ListPlot [tl,PlotRange->All]

30

25

20

15

10

5

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

120

100

Обратите внимание, несмотря на то что большинство точек расположено весьма невысоко, отдельным точкам удается занять позицию, расположенную выше всех сво­ их предшественников. Абсциссы этих точек являются сверхсоставными числами.

Сверхсоставные числа

Натуральное число п называется сверхсоставным, если у всех натуральных чисел, меньших л, количество делителей меньше, чем у п. Первым сверхсоставным числом является 1 просто потому, что у него нет предшественников. (Парадокс терминоло­ гии: 1 является сверхсоставным числом, но не относится к составным!) Вторым, ко­ нечно, идет 2, третьим — 4, четвертым — 6, пятым — сразу аж 12. Ну а как найти т-е сверхсоставное число? Вот нужная нам функция.

SuperComposite[m_]:=

Module! {t-1, tmax - l,n = l, nO=l},

While[n<m,{n0++,t = DivisorSigma[0 ,nO],

If[tmaxct,{tmax=t,n++}]}];n0]

Вот как с помощью этой функции можно составить таблицу первых т сверхсо­ ставных чисел.

tl« Table[SuperComposite[к], {к ,l,n=m}]

Однако у этой программы есть существенный недостаток: поиск в ней организован весьма неэффективно. Ведь программа для поиска очередного сверхсоставного числа повторяет все вычисления, выполненные для поиска всех предшествующих сверхсо-. ставных чисел. Поэтому она ищет очередное сверхсоставное число слишком медлен­ но. Для составления списка сверхсоставных чисел лучше использовать другую про­ грамму.

Module[{t-1,tmax * 1,п>1, n0=l, m=10000}, While[n<m,{n0++,t « DivisorSigma[0,nO],

If[tmaxct,{tmax=t,n++,Print[n,":", nO])]}]]

В составленной по результатам выполнения программы таблице для каждого сверх­ составного числа указано количество и сумма делителей, а также его каноническое разложение (табл. Б.35).

Заметьте, что в каноническом разложении сверхсоставных чисел простые числа следуют без пропусков (т.е. за Prime [i] в каноническом разложении следует Prime [i+l], а не большее простое число), а показатели степеней — в невозрастающем порядке. Все сверхсоставные числа, за исключением 1, четные. Начиная с четвертого все они делятся еще и на 3 и потому кратны 6. Начиная с пятого все они делятся не только на 2, ( но и на квадрат двойки, т.е. на 4, и потому кратны 12. Но не думайте, что если л-е сверхсоставное число делится на простое число р, то и все последующие сверхсос- \ тавные числа будут делиться на это простое число р. 25-е сверхсоставное число делит-1 ся на простое число 11, а 26- и 27-е сверхсоставные числа на 11 не делятся. Потом, \ правда, 11 опять появляется в каноническом разложении. Так что вы, возможно,1 склонны считать это исключением или аномалией. Но в таком случае придется при­ знать, что это исключение (или аномалия — как вам больше нравится?) не единичное. Ведь 53-е сверхсоставное число делится на простое число 17, а 54-е сверхсоставное число на 17 не делится. В данном случае, правда; аномалия еще короче: 17 появляется в каноническом разложении уже 55-го числа. Как вы думаете, для всякой ли степени данного простого числа найдется такое сверхсоставное число, что все последующие за ним сверхсоставные числа делятся на эту степень данного простого числа? Если вам это очевидно, то заметьте, что из этого немедленно следует, что все сверхсоставные, числа, начиная с некоторого, номер которого, конечно, зависит от заданного нату­ рального числа, делятся на это заданное натуральное число. Действительно уж, сверх­