Частное при делении с остатком — функция Quotient

Чтобы получить частное при делении (с остатком) л на т, нужно воспользоваться функцией Quotient [n,m]. Рассмотрим пример.

Quotient [16,5] 3

Для целых n и m выражение Quotient [n,m] равносильно Floor [m/n]. Однако n и т могут быть вещественными и даже комплексными числами.
Quotient[Е^10,ЕЛ8] 7 Quotient[Е^10+25*1,Е^8+41] 7-1
В случае вещественных чисел Quotient [n, m] — это такое целое число х, что d<n-m х<d+m. Однако часто нужно найти целое число х, такое, что d<n-m x<d+m. Пожалуйста, укажите сдвиг d третьим параметром.

Quotient[16,5,14]

0

Вот как можно найти частные от деления чисел 0, 1, 2, ..., 21 на 3.

Quotient[Range[0,21],3]

{0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7}

А вот частные, когда задан сдвиг 1.

Quotient[Range[0,21],3,1]

{-1,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6}

А вот частные, когда задан сдвиг 2.

Quotient[Range[0,21],3,2]

{1,-1,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6}

Пример 7.1. Графики функции Quotient.

Давайте теперь построим несколько графиков функции Quotient. Поскольку это функция двух аргументов, построим изображения поверхности z = Quotient [х, у]. Для этого используем функцию plot3D.

Деление с остатком

При выполнении операции деления с остатком получается частное и остаток. Для нахождения частного и остатка в системе Mathematica предусмотрены функции Quotient и Mod.

Китайская теорема об остатках — функция ChineseRemainder

Хитрый китаец Сунь Цю около 2000 лет назад (конечно, это могло быть и 200 лет до нашей эры, и 200 лет после начала нашей эры) открыл правило "гай-йен" ("большое обобщение"), которое является частным случаем целочисленного аналога интерполяционной формулы Лагранжа для полиномов. (Правда, примерно в то же самое время, в 100 г. н. э., греческий математик Никомах знал точно тот же частный случай.) Полностью формула была сформулирована и доказана впервые, по-видимому, в 1734 году Л. Эйлером. Сформулируем китайскую (или греко-китайскую, как назвал ее Акритас, автор одного из широко известных учебников по компьютерной алгебре?) теорему об остатках и укажем соответствующее правило (формулу).

Пусть m1, m2, ..., mr — попарно взаимно простые модули (попарно взаимно простые положительные целые числа), m = m1, m2, ... mr — их произведение, а а, u1, u2, ..., ur — произвольные целые числа. Тогда существует ровно одно целое число и, такое, что а<u<а+m, удовлетворяющее всем сравнениям u = ui(modmi). Более того,

Корни в системе остаточных классов

Задача о корзинке с яйцами представляет собой задачу о решении системы сравнений вида u=ui(modmi) с попарно взаимно простыми модулями mt. Конечно, она

допускает дальнейшие обобщения. Если не считать линейных сравнений и их систем, то наиболее простой из таких задач окажется задача об извлечении квадратного корня в системе остаточных классов, т.е. задача о решении сравнения хr = d (modn).

Критерии простоты чисел специального вида

Рассмотренные числовые функции могут успешно применяться для проверки простоты чисел специального вида. С помощью числовых функций для чисел специального вида удается построить критерии, эффективность которых часто на несколько порядков выше, чем эффективность критериев для чисел произвольного вида. Данная тема необъятна, и ниже рассмотрены только самые простые примеры применения таких критериев.

Квадратный корень по модулю — функции SqrtMod и SqrtModList

Конечно, квадратных корней в системе остаточных классов — решений сравнения х =d (mod n) — может быть более одного. Поэтому в системе Mathematica предусмотрено две функции для нахождения таких решений. Функция SqrtMod находит наименьший вычет, а функция SqrtModList — Список всех вычетов.

Наименьший квадратный корень по модулю — функция SqrtMod

Выражение SqrtMod[d, n] представляет собой наименьший неотрицательный квадратный корень из d по модулю n, т.е. такой наименьший неотрицательный вычет m, что m2sd(modn). Но это, конечно, в том случае, если такое т существует. Для этого d, понятно, должно быть полным квадратом по модулю и, т.е. символ Якоби .jacobiSymbol [d, n] должен быть равным 1. Это условие также достаточно, если и является простым числом. Для простых n система Mathematica использует алгоритм Шенкса (Shanks). Для примера найдем самое маленькое неотрицательное целое число, такое, что его квадрат равен 3 по модулю 11.
SqrtMod[3,11] 5
Этот результат легко проверить.

Mod[Range[11]^2,11]

{1,4,9,5,3,3,5,9,4,1,0}

Как видите, только квадраты чисел 5 и 6 по модулю 11 равны 3. Если квадратный корень из d по модулю п не существует, SqrtMod [d, n] останется невычисленным.

Остаток от деления — функция Mod

Чтобы получить остаток от деления n на m, нужно воспользоваться функцией Mod[n,m]. Наименьший возможный остаток в этом случае равен нулю, а наибольший... Как вы думаете, чему равен наибольший возможный остаток? "Конечно, m-1", — возможно, подумали вы. Ну, что же, я, конечно, приветствую ваши глубокие познания в теории чисел, ибо именно так написано во всех классических учебниках по этой дисциплине, если, конечно, именно в этом месте нет какой-либо досадной опечатки. Но должен вас разочаровать: вы не угадали. Зато, надеюсь, вам будет приятно узнать, что возможности функции Mod значительно шире, чем требуется для решения задач из задачников по классической теории чисел. Дело в том, что аргументы этой функции могут быть не только целыми (это предусмотрено классическими учебниками теории чисел), но и вещественными и даже комплексными! А во множестве вещественных чисел, как вы, надеюсь, еще помните, полно сюрпризов... Но сначала давайте рассмотрим простейший случай целых аргументов.

Mod[7,5]

2

Ну вот, при делении 7 на 5 остаток равен 2. Просто и понятно, даже в уме можно вычислить. Вот еще один пример.

Мод[3^10,5]

4

Тоже в уме, и тоже просто и понятно. Но вот несколько примеров с вещественными числами.

Первообразные корни по модулю n

Показатели — функция MultiplicativeOrder

Наименьшее натуральное решение т показательного сравнения km =1(modn) называется показателем числа k по модулю п. (Иногда это выражают иначе: говорят, что k принадлежит показателю т по модулю n.) В этом случае можно сказать, что k является корнем m-й степени из единицы в кольце классов вычетов по модулю т. Вот пример: 2 принадлежит показателю 4 по модулю 5.

Table[Mod[2го, 5], {m, 10}]

{2,4,3,1,2,4,3,1,2,4}

Для вычисления показателя т в системе Mathematica предусмотрена функция

MultiplicativeOrder[k, n].

MultiplicativeOrder[2,5] 4

Конечно, показатели существуют не во всех случаях, а только тогда, когда k ч п взаимно просты. Если показатель не существует, функция MultiplicativeOrder [k, n] остается невичисленной.

Функция MultiplicativeOrder может иметь еще третий параметр — список. Список {а,, а,,..., as} в вызове MultiplicativeOrder [k, n, {а,, а,, ..., as } ] используется тогда, когда нужно найти наименьшее т, удовлетворяющее хотя бы одному из сравнений km =a, (mod/i). 3 является наименьшим натуральным числом, удовлетворяющим хотя бы одному из сравнений 2m =5 (mod n) и 2m =8(modn).

Table[PowerMod[2,m,11],{m,10}]

{2,4,8,5,10,9,7,3,6,1}

Вот как это можно вычислить.

MultiplicativeOrder[2,11,{5,8}]

3

Пример 7.6. Длина периода систематической дроби по основанию b. Вот функция, которая вычисляет длину периода систематической дроби, представляющей рациональное число r по основанию b.
DigitCycleLength[r_Rational,b_Integer?Positive]:= MultiplicativeOrder[b,FixedPoInt[Quotient[#,GCD[#,b]]&, Denominator[r]]]
Вот пример. Длина периода дроби 1/49 в десятичной системе равна 42.

DigitCycleLength [1/4.9,10]

42

А вот и подтверждение.
N[1/49,151] 0.020408163265306122448979591836734693877551 020408163265306122448979591836734693877551 020408163265306122448979591836734693877551 02040816326530612244897959
Что такое первообразный корень по модулю n

Решая сравнение km =l(modn) относительно k, можно заметить, что при некоторых n находятся такие k, которые принадлежат довольно большим показателям m. В частности, при некоторых n случается, что k принадлежит показателю, который равен числу вычетов, взаимно простых с n. Такие числа k называются первообразными корнями по модулю n. Конечно, по составному модулю в большинстве случаев первообразных корней не существует. Первообразные корни существуют только по модулям 2, 4, рi и 2 рi (здесь р — произвольное нечетное простое число). Для вычисления первообразных корней по модулю и в системе Mathematica предусмотрена функция PrimitiveRoot [n].

PrimitiveRoot[5]

2

Если первообразного корня не существует, функция остается невычисленной.

PrimitiveRoot[11*13] PrimitiveRoot[143]

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

Простые числа Мерсенна тест ЛюкаЛемера

Простые числа Мерсенна, тест Люка-Лемера

Наибольшее простое число поймано решетом Эратосфена.

Конечно, решето Эратосфена годится для поиска простых чисел Мерсенна не более чем консервная банка для плавания через Атлантический океан. Гораздо более пригодна для этой цели функция PrimeQ. С ее помощью мы нашли все те индексы простых чисел Мерсенна, которые не превышают 5000. Дальнейшее продвижение оказалось практически невозможным. Однако есть другой метод проверки простоты чисел этого вида. Его опубликовал Э. Люка (Lukas2) в 1878 году, а в 1930 году усовершенствовал Д. X. Лемер. Он основан на следующей теореме.

Если р>2 — простое число, то число Мерсенна Мр = 2p -1 является простым тогда и только тогда, когда bр_r = О, где последовательность L; определяется так:

L0 =4, Li+1=(Li2-2)mod(2i-l).

Совершенно элементарное доказательство этой теоремы имеется во многих книгах; в частности, его можно найти во втором томе трехтомника Кнута. Чтобы сократить доказательство, можно также заметить, что критерий Люка основан на малой теореме

Ферма для чисел из полей Q(v5) или Q(v3). Тест Люка позволил проверить вручную все простые числа до МР7. Когда для проверки простоты стали применяться ЭВМ, началась настоящая гонка. Очередные новые простые числа Мерсенна рассматривались как свидетельство быстрого роста возможностей ЭВМ. Чтобы убедиться, что Л/819] является составным, Д. Дж. Уилер потратил около 100 часов машинного времени ILLIAC I — самой быстрой ЭВМ выпуска пятидесятых годов. Гурвицу на IBM 7090 для этой же цели потребовалось лишь 5 часов в 1962 году. В 1964 году Гиллис сделал это на ILLIAC II за 49 минут. А в 1971 году Такерман потратил на это только 3 минуты на IBM 360/91. (Но то были суперЭВМ, а я на своем весьма слабеньком ПК на это потратил 4,125 секунды.) Проверка простоты М1тз на ILLIAC II заняла 2 часа 15 минут, и всего лишь 8 минут на IBM 360/91. (Но это столько нужно суперЭВМ, а моему старенькому ПК нужно всего лишь 9,672 секунды.) Найденное очередное простое число Мерсенна становилось визиткой фирмы. Например, доказательству простоты числа

М112,з Иллинойский университет посвятил выпуск фирменного конверта. IBM в долгу не осталась: она выпустила конверт, посвященный доказательству простоты М19937 (это 6002-значное число, найденное Б. Такерманом 4 марта 1971 года, довольно долго было рекордсменом). Проверка простоты этого числа и у меня заняла изрядное время - 42 094 секунды. с помощью функций Mod и powerMod несложно запрограммировать тест Люка- Лемера. Сначала дадим нужные определения.
Mn[n_]:=Module[{t=4}, Do[t=Mod [PowerMod[t, 2,mn] -2,mn],<i, n}]; t]; MPrime[p_]:=Mn[p-2,Mn[p]]==0;
Поскольку единственным простым числом Мерсенна Мр с четным индексом р является Я,, можем ограничиться поиском только нечетных индексов р. (Конечно, программа при этом пропустит число Мг = 3, но разве мы можем о нем забыть?) Вот нужная нам программа поиска нечетных индексов р простых чисел Мерсенна М „.

Block[{p=3}, While [p<45000, {If[MPrime[р],Print[p]], p=NextPrime[p] } ] ]

Даже на весьма слабеньком компьютере всего за несколько часов вы можете найти все нечетные индексы р первых 24 простых чисел Мерсенна известных до 1980 года: 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937. Здесь, конечно, только 23 числа, поскольку индекс первого простого числа Мерсенна М2 = 3 четный: р = 2.

Надеюсь, вы о нем не забыли, так что не забудьте и отпечатать специальные конверт. Заметьте что данную программу очень легко распараллелить и организовать поиск на нескольких ЭВМ. Кроме того, данную программу легко модифицировать так, чтобы поиск продолжался после уже проверенных чисел. Впрочем, возможно, программу придется модифицировать так, чтобы она время от времени подавала признаки жизни", даже если не успевает найти простое число Мерсенна. Это можно сделать, например, так.
Block[{р=19937,1=1},p; While [p<45000, {If [MPrime [p], Print [p]], p=NextPnme [p] , If[Mod[i++,500]==0, Print["***p=",p]] HI
Так что если не поленитесь потратить ночку-другую на вычисления, то найдете и другие простые числа р, при которых р-е число Мерсенна Mf = 2'-l является простым. В частности, вы сможете найти 6533-значное простое число Мерсенна Л/,,70, (найдено калифорнийскими школьниками Никкелом и Ноллом в 1978 году), 6987-значное простое число Мерсенна М23209 (найдено Ноллом), 13395-значное простое число Мерсенна Мш„ (это 27-е простое число Мерсенна найдено Д. Словинским в 1979 году), 25962-значное простое число Мерсенна М86243 (это число Мерсенна найдено Дэвидом Словинским в январе 1983 года). Если хотите, проверьте, не пропустил ли я чего-нибудь и сможете ли вы продвинуться дальше. У меня проверка простоты М,1701 заняла 53,547 секунды, М2Ш) - 64,25 секунды, Мшу, - 350,562 секунды (ого, почти 6 минут!), Мим - 1845,34 секунды (это чуть больше получаса). Думаю, что дальнейшее продвижение по данной программе весьма затруднительно. В данном случае либо нужен компьютер со значительно более высоким быстродействием, либо нужно изменить программу так, чтобы большинство составных чисел отсеивалось еще до применения критерия Люка. Казалось бы, перед применением критерия Люка можно проверить, что число Мр не удовлетворяет сравнению ам' = a(modMp) при некоторых а. В качестве а удобно взять, например, число 3. Можно было бы также попытаться проверить другое свойство простых чисел. Однако при этом нужно тщательно следить за тем, чтобы все эти дополнительные проверки не снижали быстродействие программы. Время проверки сравнения an s=a(modMp) может оказаться, например, примерно равным времени проверки по критерию Люка—Лемера. Тогда, понятно, такая дополнительная проверка только замедляет выполнение программы. Так что дальнейшее продвижение требует изобретательности.

Дальше идет степень 110503. В 1983 году была найдена степень 132049, а в 1984 — 216 091. Поиском степеней на суперкомпьютерах прославился в 90-х годах XX столетия Дэвид Словинский. Вместе с Полем Гейджем он получил следующие индексы простых чисел Мерсенна: 756 839, 859 433, 1 257 787. Но степени 1 398 269 и 2 976 221 были найдены Жоэлем Арменгодом (Joel Armengaud) и Гордоном Спенсом (Gordon Spence) на персональных компьютерах по программе, разработанной Георгом Вольтманом (George Woltman) в 1996 году. Предварительная проверка Л/2,76,,, на компьютере с процессором Pentium с тактовой частотой 100 МГц заняла 15 суток в августе 1998 года! 27 января 1998 года Роланд Кларксон (Roland Clarkson) обнаружил простоту Л/3021377, а 1 июня 1999 года Найян Хьяратвала (Nayan Hayratwala) — простоту Af6972593. Впрочем, люди стремятся к рекордам, и после 1983 года числа проверялись не подряд, так что могли что-то и пропустить! Правда, добровольцы тщательно потом все просмотрели до миллиона!

Как из этого видно, критерий Люка—Лемера применяется только после некоторого предварительного отбора, которому уделяется огромное внимание. Давайте попробуем найти хотя бы какой-нибудь очень простой (а, значит, и довольно грубый) метод отсева показателей р, для которых числа Мерсенна Мр не являются простыми. Пусть s— показатель 2 по некоторому простому модулю q: Т =1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Поскольку Мp = 1n -1 оно делится на простое число q, если р является показателем 2 по простому модулю q. Так что такие индексы р чисел Мерсенна можно отсеять сразу, если Мр # q. Поэтому для предварительного отсева нам понадобится таблица показателей 2 по простым модулям q. Причем, чтобы уменьшить таблицу, из нее можно вычеркнуть все составные показатели. Чтобы построить таблицу, нам понадобится следующая функция.
f[n_]:= Block[{q= Prime[n], s=MultiplicativeOrder[2,q]}, If[NumberQ[s],If[PrimeQfs],s]]]
Эта функция по заданному номеру n находит простое число q = рn, а затем — 5 (показатель 2 по найденному простому модулю q, если он существует). Если оказывается, что показатель 2 по простому модулю q существует, проверяется, является ли он простым числом. Если оказывается, что найденный показатель 2 по простому модулю q является простым числом, он возвращается в качестве значения функции. (В противном случае функция возвращает Null.) С помощью этой функции легко строится нужная нам таблица простых показателей 2 по простым модулям q.

t=Union[Sort[DeleteCasestArray[£,100000, 4] ,Null]]] ;

Функция Array [f, 100000, 4] генерирует следующий список из 100000 элементов {f[4], f[5],...}- Функция DeleteCases [Array [f ,100000, 4] ,Null] удаляет из него элементы, равные Null. Затем функция Sort сортирует этот список, а функцияUnion рассматривает его как множество и тем самым исключает из него повторяющиеся элементы.

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

tl=Union[Sort[DeleteCases[Array[f,100,4],Null]]]

{3,5,7,11,23,29,37,43,73,83,131,179,191,239,251}

Понятно, что это очень мало. Но даже если бы мы исходили из тысячи простых чисел, у нас бы получился список из 80 элементов.

существует весьма эффективный критерий

Простые числа вида k*2n +1

Для чисел вида k*2n+ 1 существует весьма эффективный критерий простоты. Он состоит в проверке сравнения а2n-1 =-1 (mod k*2n +1) для некоторого а. Однако выбор этого а зависит от k. Оказывается, нужно различать случаи, когда k не делится на 3 и делится на 3. Случай, когда k не делится на 3, совсем прост.

Случай, когда k не делится на 3

Если k не делится на 3, то, как заметил Прот (Proth) в 1878 году, числа k*2n +1 являются простыми при kn + 1 тогда и только тогда, когда 32n-1-1 (mod k-2n+l). Впрочем, эта традиционная формулировка критерия Прота несколько некорректна. В ней, например, (молчаливо!) исключается случай n = 1, k = 1. Для n =1, k - 1 имеем k = k3 = 2+1= 2" + 1, хотя З2""* =3sO (mod /n2n+1), причем *-2"+1 =3-простое число. Дело в том, что если число k-2n +1 простое, то в традиционной формулировке критерия Прота число3 должно быть квадратичным невычетом по модулю k-2n + l. Но при и= 1, k= 1 число k2n+l =3. Впрочем, n- 1, k- 1 — единственное решение уравнения k* 2n +1 =3 в целых числах, отличных от 0. (Уравнение k-2" + 1 =3 в целых числах имеет всего два решения: указанное только что решение n= 1, k= 1 и n = 0, k= 2.)

Разыскивая простые числа вида k*2n +1, конечно, нельзя ограничить перебор по и только простыми числами, но все равно многие значения отсеиваются тривиальным образом.

Пример 7.7. Простые числа вида 5-2n + 1. Рассмотрим, например, случай k = 5. Тогда числа вида 5*2n +1 делятся на 3 при четных п. Так что перебор можем вести только по нечетным и.

Используя функцию PowerMod, очень легко запрограммировать критерий простоты.

MknPrime[k_,n_]:=Module[{t = k*2An+l},

If[k<=2An+l,PowerMod[3,(t-1)/2,t]==t-l,PrimeQ[t]]]

А вот и программа для перебора по нечетным п.

Mkn[k_,nl_]:=Block[{n=l},

While [n<=nl, {If[MknPrime[k,n],Print[п]], n+=2}]];

Теперь можем выполнить перебор. Mkn[5,300000]

Так можно получить (если хватит терпения) следующие значения я: 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313, 4687, 5947, 13165, 23473, 26607, 125413, 209787, 240937.

Впрочем, при дневном счете терпение обычно улетучивается после печати числа 13165, если не раньше. Конечно, метод перебора можно усовершенствовать, заметив, что если остаток от деления и на 3 равен 2, то число 5*2n +1 делится на 7. Так что числа, дающие в остатке 2 при делении на 3, можно при переборе пропустить. Можно также пропустить числа, дающие в остатке 1 при делении на 10, поскольку тогда число 5*2n + 1 делится на 11. Можно, конечно, пойти и дальше. Можно, например, взять несколько небольших нечетных простых чисел д, для которых существует решение сравнения 5-2n + 130 (mod q). Пусть s— показатели 2 по модулю q: 2s=1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Тогда при всех n^t (mod s) 5*2n + 1 = 0 (mod q). Если q не является числом вида 5*2n +1, все числа nst (mod s) можно опустить при переборе. Если же q является числом вида 5*2n +1, то нужно оставить только то число rmt (mod s), при котором 5*n + 1 = q. Эта идея вполне реализуема, но не слишком ли она усложняет перебор?

Давайте попробуем. Вот функция, которая по заданному номеру я простого числа q находит t — решение сравнения 5* 2n +1 = О (mod q) и i — показатель 2 по модулю q, если такое решение существует.
:[n]:= 51ock[{q= Prime[n], s=MultiplicativeOrder[2,q], t=MultiplicativeOrder[2,q,{-PowerMod[5,-I, q]} ] }, If[NumberQft],fs,t}]]
Теперь с помощью этой функции можно сгенерировать таблицу остатков и соответствующих им модулей.

и основу основ модулярной арифметики

Резюме

Мы рассмотрели определение частного (функция Quotient) и остатка (функция Mod), а также возведение в степень в модулярной арифметике (функция PowerMod) и основу основ модулярной арифметики — китайскую теорему об остатках (функция ChineseRemainder). Кроме того; мы затронули вопрос об извлечении квадратных корней (функции SqrtMod, SqrtModList и JacobiSymbol). Но мы не ограничились корнями второй степени, а научились находить первообразные корни по модулю n (функция PrimitiveRoot), а также показатели (функция MultiplicativeOrder). Как оказалось, некоторые из рассмотренных функций используют каноническое разложение (функцию Factorlnteger) и потому не могут справиться с вычислениями при очень больших аргументах. Однако на реальных примерах мы убедились в том, что эти функции очень полезны и вполне пригодны даже тогда, когда вычисления ведутся с очень большими числами, например с числами, близкими к тысячным, десятитысячным, стотысячным и даже миллионным степеням двойки.

Возведение в степень в модулярной

Возведение в степень в модулярной арифметике — функция 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, нужно просто вычислить это число с разрядностью не менее тысячи знаков. Вот как это делается.
М[9^(9^9),1000] 4.281247731757470480369871159 30563521339055482241443514174753723053523 887471735048353193665299432033375060417533 64763100078032613904733860832080206037470612 809165574132086446019861999614520310524428581489598115 1471949351767796559302159393385015023969426231 0529675816569433334631474925538494859337781208762 495721650419522060180457130151786405101459407 904194866332733667183065441076023482363342793388473 449171490713928387636703470733221615842638847026446 505858035582482311577827786618011472099436290690473438 366488664695023381735331493288811517612485971201533575 64439876059956217339548503950536965544532955477621833381 799037537429866036175410766960904718339923933145342547022 698333065128258703520736236 343330809161939992399143539 9517426262619225044491488935534629633876424, 710803619094832833935338326811681684096752173716022 71240386424109448631241673361631602584738577273169933875 567294188775379238762791518151971 69574861839692092170993 60780264476440839592643445485180078094839593328 539827016475025109538Х10369693099
Почти так же можно вычислить и последнюю тысячу знаков.
Mod[9^(9^9),10^1000]//Timing{260.64 Second, 164378947574778447311427807670372670 0326359025082234292387746462391127 9751529028988405927046285969119001418 842032015433264756391857718597649 204912230323811027210136918 3684943285741373762637969125845614123744406 01020026085922354 10622770718702230402359356419151296996286668460066302 9835137 9027215796574565344432784903341994543575575416975966278964106 12 7038799025612835366795058993611717249028581457173391518760 2283281383558665788995350272253954345165983917336427507154331 749386377957650223307 168958637197192110578737857336943212457 7155212755139983177854767167859 12996450672962748373653022152 34320507478340927905653712738326405359097 6996351343597753799 283680752817548382724478144536940979972304718417625 894479515 4018072624283659761429188348967918815377285476781074966161266 1854762666853235529005571888491679885547006847358268508973918 700851075402818853925349052912288203971972 4032235787006073283877358282 617004315060225040660196165699439754361026855266374036682906 1901749234943241787 99359681422627177289}
Вычисление, как видите, заняло более четырех минут (260,64 секунды). Но гораздо быстрее результат можно получить вот так.
PowerMod[9,9^9,10^1000]//Timing {0.015 Second, 1643789475747784473114278076703726700...2627177289}
(Здесь середина пропущена.) Это вычисление заняло лишь 0,015 секунды. Это более чем в тысячу (точнее, в 17376) раз быстрее!

Пример 7.4. Графики функции Power Mod.

Давайте теперь построим несколько графиков функции PowerMod. Поскольку это функция двух аргументов, построим изображения поверхности z = PowerMod[x, у]. Для этого используем функцию Plot3D.