Иллюстрированный самоучитель по Mathematica 5

Возведение в степень в модулярной арифметике (функция Power Mod)

Иногда приходится решать задачи такого типа:

  • найти вычет аb по модулю n;
  • найти последние m цифр числа аb в системе счисления с основанием с.

Конечно, совсем несложно написать что-нибудь вроде Mod[a^b,n] или Моd[а^b, с^m]. Однако все дело в том, что в исследовательских задачах b может быть столь велико, что для вычисления аb не хватит памяти. Кроме того, по мере вычисления аb часто бывает так, что требуется все больше памяти и начинает работать подкачка, что очень часто приводит к пробуксовыванию. А тогда процессор практически простаивает, и даже самая простая операция выполняется фантастически долго.

Пример 7.3.
Наибольшее число, которое можно записать тремя цифрами. Число 999 имеет 369 693 100 цифр, т.е. более трети миллиарда! Еще в 1953 году было известно, что это число начинается цифрами 428 124 773 175 747 048 036 987 115 930 563 521 339 055 482 241 443 514 174 753, а заканчивается цифрами 24178799359681422627177289. Какие цифры между ними, не было известно и в 1959 году. Ведь если это число напечатать более или менее четко на полоске бумаги, то эта полоска оказалась бы длиной 1200, а может и 1800 км. Если же напечатать это число в книге так, чтобы на каждой странице помещалось 14 000 цифр (на странице обычно помещается 2.5-3 тысячи знаков), то такая книга состояла бы из 33 томов по 800 страниц в каждом.

Но с помощью системы Mathematica несложно вычислить, например, первую и последнюю тысячу цифр числа 999. Чтобы вычислить первую тысячу цифр числа 999, нужно просто вычислить это число с разрядностью не менее тысячи знаков. Вот как это делается.

M[9^(9^9), 1000]
4.281247731757470480369871159
30563521339055482241443514174753723053523
887471735048353193665299432033375060417533
64763100078032613904733860832080206037470612
809165574132086446019861999614520310524428581489598115
1471949351767796559302159393385015023969426231
0529675816569433334631474925538494859337781208762
495721650419522060180457130151786405101459407
904194866332733667183065441076023482363342793388473
449171490713928387636703470733221615842638847026446
505858035582482311577827786618011472099436290690473438
366488664695023381735331493288811517612485971201533575
64439876059956217339548503950536965544532955477621833381
799037537429866036175410766960904718339923933145342547022
698333065128258703520736236343330809161939992399143539
9517426262619225044491488935534629633876424
710803619094832833935338326811681684096752173716022
71240386424109448631241673361631602584738577273169933875
56729418877537923876279151815197169574861839692092170993
60780264476440839592643445485180078094839593328

539827016475025109538 Х 10369693099.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.