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

функция FactorlntegerECM:

поиск делителей 5011 -го числа Мерсенна М 50и

функция FactorlntegerECM иногда может находить делители таких чисел, которые можно смело отнести к разряду супервеликанов. Еще в середине прошлого столетия было известно, что 5011-е число Мерсенна Мт1 — составное. Вот этот супервеликан.

М5011=2А5011-1

2892 73248

18215 44523 43850 93980 49069 73935 38993 66777 94020 72344 33199 83537

80118 37864 98571 89665 30696 62520 60126 33153 70867 43773 75010 89460 36731 76849 12068 98836 81585 63186 79404 10406 20337 17632 61432 7-3229 73607 80769 24339 46895 10452 28771 76908 35845185627 44429 76355 54782 04099 25746 18760 67696 96063 23006 39170 48637 42056 14018 45193 88981 05470 47861 79314 13138 72572 68595 75499 07080 74755 06923 88499 54148 47862 97635 61834 21202 71529 86149 35598 25176 42702 02090 90665 35410 23964 21644 89206 45446 41294 31483 87457 76257 63207 21682 93460 49711 89996 92761 78393 67626 95270 58100 37487 25182 55133 55860 15109 75055 91340 94143 04150 50397 15118 45353 21042 92396 18396 78924 30244 05348 03633 94510 78115 10641 83167 54527 10042 21819 25041 44149 71143 19467 61569 65335 22944 44713 57813 79906 23282 26813 19799 32802 65991 41782 55062 29513 94226 07275 47517 31998 53000 29529 82411 02019 37076 56303 75449 66063 86005 78206 68496 57753 47991 02291 73607 06957 38010 85140 30501 27004 10279 59700 32021 73095 67468 52956 23131 11833 95642 97883 64552 48115 29835 96561 17975 01081 83613 33181 30625 00580 77598 31855 31571 94039 96761 51867 59529 60399 03825 00082 28568 54149 53386 06915 42034 44056 30877 45117 53328 95679 17966 57822 34608 28710 09060 40540 40721 31089 98796 83376 81783 78680 35169 27956 25717 27962 40555 14988 56928 07408 96225 96893 40065 36632 19098 49038 19691 34788 34539 80793 43327 82336 29271 74360 48324 38609 66703 74228 28936 98294 54090 18994 05347 20351 63614 73069 97125 78508 96137 79576 85906 59571 73807 86607 50208 46764 84960 83000 12765 14784 84324 44106 61802 23016 62025 74917 24801 37626 55457 05709 71141 81636 30280 79676 70353 48726 64786 99764 40340 04214 82889 79020 07933 58672 17343 79810 18298 19840 90304 02047

С помощью системы Mathematica можно почти мгновенно убедиться, что это чис­ ло составное.

PrimeQ[М5011]

False

Однако неплохо было бы найти хотя бы какой-нибудь его делитель.

m=FactorIntegerECM[М5011]

Системе Mathematica потребуется менее 36 секунд, чтобы найти делитель т = 80177. Теперь проверим, прост ли найденный делитель.

PrimeQ [m]

True

Оказывается, да! Есть шансы разложить 5011-е число Мерсенна Л/5011 на простые множители? Давайте попытаемся. Для этого разделим 5011-е число Мерсенна М5Ш на найденный делитель.

п=М5011/ш

3607933050402914206615998850105478802342192108432518312277128353312518

5674668109130036875047664856579974720352578350117552551163097561356113

6072674667496368268698056849994807957801044281065313092379266297652632

3574451173891310283318500870544365027152936535098828350736116421455110

4644082934264956307235165818258940193095191155990777563215854296208148

8151301793344667608514448986070611537008310346046068052580718537761339

3698135503194708762976994081396528075182091842121346610833896828887485

1886360948700210318361507427363816620509015498035784698237139505021927

0053137397896959668247039973581447034988867637038098631092555365137655

8324139430265814160233501396873346713741044146494916802164408513412901

8649074088553990299786614837490879298476399225807245435972726592782591

3180862583668204477287122998348660815529203708985718984533187331865215

4621464264128274946808680756366566136119768578215986269358289338561977

1945172746527802937475523040502405093496966088255704233365593090213402

4422862761082305897000698464932048519519735843091435629177483414758815

2872964555666410345044193311060603920580805132506813635254102527890546

5618917598029020744609490875010200025056590539548000865164846649900073

5486920043720743846032251435735025934625681228543930350877220321267876

5843309104275191578178464281523536407061393890488368317543901378033694

2275799354548165933032729434232166882106065608611721887189249786567551

2250467212684662230194205280405045695481844793100768799557831909138781

4377672801095550856458812357771311

Но простое ли число ril Давайте проверим.

PrimeQ[п]

False

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

Функция FactorlntegerECM:

поиск делителей М13 -го числа Мерсенна ЛТ8191=

Но все же ситуация не столь безнадежна. Некоторые специалисты по теории чи­ сел, например, долгое время считали, что если число Мерсенна Мп является простым, то и число М Мптоже простое. Это действительно так для четырех наименьших про­

стых чисел Мерсенна. Но лишь в 1953 году Д. Ю. Уиллер показал, что для пятого

более чем десятилетия после открытия Уиллера не удалось найти ни одного его про­ стого делителя. С помощью функции FactorlntegerECM это можно сделать за счи­

танные минуты (само число М м^ в распечатке опущено).

ММ13=2Л8191-1 m=FactorIntegerECM[ММ13]

338193759479

С другой стороны, давно было известно, что Л/17 и М19— простые числа. Кроме того, еще в 1957 году было доказано, что М м^ делится на п1 = 1768(2,7-1)+1 = 231733529, а

М мп — на п2= 120(219“ 1)+1 = 62914441. Тем не менее функция FactorlntegerECM,

не говоря уже о функции Factorlnteger, не может обнаружить ни одного нетриви­ ального делителя М м^ или М м Интеллект человека сильнее. Мораль: Хотя всех

проблем теории чисел решить не может даже функция FactorlntegerECM, воспри­

нимать это следует без излишнего пессимизма...

Резюме

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

Если же функция Factorlnteger со своей работой за приемлемое время не справляется, можно сначала найти только те делители, нахождение которых не соста­ вит труда для нее, — именно для этого предназначена опция FactorComplete->False. Все же чаще приходится прибегать к имеющейся в пакете теории чисел функции FactorintegerECM. Однако эта функция за один раз находит только один делитель, притом не обязательно простой. Кроме того, она может зациклиться, если в качест­ ве аргумента получит простое число. Так что перед вызовом этой функции нужно проверить, не является ли ее аргумент простым числом — это делается с помощью функции PrimeQ. (Как правило, функция PrimeQ работает очень быстро.) Получив очередной делитель, число можно разделить на него и проверить, не является ли част­ ное простым числом. Если частное окажется простым числом, то фактически кано­ ническое разложение можно считать полученным, если известны канонические раз­ ложения найденных ранее делителей. Если же частное или какой-нибудь делитель окажется числом составным, к нему можно попытаться снова применить функцию FactorIntegerECM. Повторяя эту процедуру достаточное число раз, иногда (для от­ носительно небольших великанов часто) удается найти каноническое разложение.

Если же и этот метод не приводит к успеху, помочь могут различные формулы (например, разложения суммы или разности степеней и т.п.) и предварительно со­ ставленные таблицы. Благодаря системе Mathematica к таблицам приходится прибе­ гать существенно реже, чем в докомпьютерную эпоху. Более того, сами таблицы можно составить с помощью программ, написанных на языке программирования, встроенном в систему Mathematica. Однако, как и в эпоху Эйлера и Гаусса, таблицы незаменимы при поиске нетривиальных закономерностей в канонических разложениях чисел того или иного вида. Однако представление, возвращаемое функцией Factorlnteger, не­ сколько “однолинейно” и потому удобно скорее для дальйейшего использования в качестве аргумента других функций, чем для чтения человеком. Хотя это представле­ ние система Mathematica может преобразовать в различные форматы, подчас проще написать макрос, преобразующий его в привычный вид.

Задачи

Задача 4.1. Факторизовать число 1234567891011121314151617181920.

Глава 5

Арифметика: простые числа

Вэт ой главе...

♦Тест на простоту

♦Функции PreviousPrime и NextPrime и случайные простые числа

♦Таблицы простых чисел

♦Число простых чисел, не превосходящих х (функция РптеРЦх])

♦Резюме

♦Задачи

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

Учебник математики для 5—6 классов (Л. Н. Шеврин и др.)

Тест на простоту

Чтобы сказать, является ли простым заданное число из 15 или 20 цифр, не хватит всей жизни, даже если использовать все, что уже известно.

Мерсенн, XVII в.

Что задача различать простые и составные числа, а послед­ ние разлагать на простые множители, принадлежит к важ­ нейшим и полезнейшим задачам во всей арифметике и что она занимала ум как древних, так и современных математи­ ков, настолько известно, что было бы излишним тратить на это много слов. Тем не менее следует признать, что все до сих пор предложенные методы или ограничиваются частны­ ми случаями, или настолько громоздки и трудоемки, что в основном едва ли могут быть применимы к большим чис­ лам ...; достоинство науки требует, чтобы прилежно усовер­ шенствовались все вспомогательные средства, могущие по­ мочь в решении этой знаменитой проблемы.

К. Ф. Гаусс. “Disquisitiones Arithmetics" ( “Арифметические исследования 1

функция PrimeQ

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

Вальтер Боро. Дружественные числа. Открытая лекция, прочитанная при вступлении в должность в Боннском университете

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

Вальтер Боро. Дружественные числа. Открытая лекция, прочитанная при вступлении в должность в Боннском университете

В предыдущей главе, разлагая числа на простые множители, нам уже приходилось проверять числа на простоту. Как вы помните, для этого служит функция PrimeQ, на­ звание которой заканчивается прописной буквой Q (question — вопрос), что означает, что она в качестве значения выдает True или False. Числа, ассоциированные с 1 (например, 1 и -1), она к простым не относит.

PrimeQ[1]

False

PrimeQ[-1]

False

Кроме того, как и следует ожидать, она применима и к целым отрицательным чис­ лам, причем PrimeQ[—n] = PrimeQ[п]. Более того, она применима к целым гауссо­ вым числам, и если ее аргумент — число с ненулевой мнимой частью, она осуществ­ ляет проверку на простоту именно в области гауссовых чисел. Однако если вы хотите в кольце гауссовых чисел проверить на простоту число с нулевой мнимой частью, придется указать опцию GaussianIntegers->True.

PrimeQ [5]

True

PrimeQ[5+0 I]

True

PrimeQ[5, G a u s s ia n I n t e g e r s - > T r u e ]

False

Пример 5.1. Составим таблицу нескольких первых чисел Ферма с указанием их простоты. Вот что надо ввести в блокнот.

Table[{2 гП + 1 , PrimeQ[22" + 1 ] } , {п, 0 , 10}]

В результате получим (конец обозначен многоточием) следующее.

({3,True}, (5,True},{17,True},{257,True},{65537,True},{4294967297, False},{18446744073709551617,False},{3402823669209384634633746074

31768211457,False},

Все это удобнее свести в таблицу (табл. Б. 18).

Видите, как ошибся Ферма! Это потому, что он не использовал предикат PrimeQ.

Пример 5.2. Составим список всех натуральных «<5000, для которых число Мерсенна Мя является простым. Для этого можно ввести в блокнот следующую программу.

М[п_)=2Лп-1;Do[ If[PrimeQ[M[n]],P r i n t [ n , , {n, 5000} ]

Здесь вначале определена функция М п, а затем записан цикл, в котором проверя­

Конечно, есть гораздо лучший метод проверки чисел М ерсенна на простоту.

Пример 5.3 (задача А. Рихнера). Составим список всех натуральных л^5000, для ко­

торых число 2" 4-3 является простым. Для этого можно ввести в блокнот следующую

программу.

М[п_]=2Лп+3;Do[ If[PrimeQ[М[n]] , P r i n t [ n , " , " ] ] , {n, 5000} ]

Вначале определена функция, вычисляющая число, а затем записан цикл, в кото­ ром проверяется простота ее значений. Будут выведены следующие числа: 1, 2, 3,

Пример 5.4. Составим список всех натуральных л£50(Ю, для которых число 2-2я4-1 является простым. Для этого можно ввести в блокнот следующую программу.

М[п_]=2*2Лп+1; Do[ If[PrimeQ[M[n]] , P r i n t [ n , " , " ] ] , {n, 5000} ]

Здесь вначале определена функция, вычисляющая число, а затем записан цикл, в котором проверяется простота ее значений. Будут выведены следующие числа: 1, 3,

7, 15.

Результат можно было угадать. Ведь числа вида 2-2" 4-1 могут быть простыми толь­

ко тогда, когда л41 имеет вид 2т, иными словами, только при п = 2т—1.

Пример 5.5. Составим список всех натуральных я£5000, для которых число 3-2”4 1 является простым. Для этого можно ввести в блокнот следующую программу.

М[n_]=3*2лп+1; Do[ I f [PrimeQ[М[n]] , P r i n t [ n , " , " ] ] , {n, 5000} ]

Вначале определена функция, вычисляющая число, а затем записан цикл, в кото­

Здесь вначале определена функция, вычисляющая число, а затем записан цикл, в ко­ тором проверяется простота ее значений. Будут выведены следующие числа: 2, 6, 14.

Результат можно было угадать и в этом случае. Ведь числа вида 4-2л+1 могут быть

простыми только тогда, когда п+2 имеет вид 2т, иными словами, только при п = 2т-2.

Пример 5.7. Составим список всех натуральных пй5000, для которых число 5 2" 4 1 вляется простым. Для этого можно ввести в блокнот следующую программу.

М[n_]=5*2лп+1; Do[ If [ PrimeQ [М [n] ], P rint [n, ","]] , {n, 5000} ]

Здесь вначале определена функция, вычисляющая число, а затем записан цикл, в котором проверяется простота ее значений. Будут выведены следующие числа: 1, 3,

7, 13, 15, 2 5 , 3 9 , 5 5 , 7 5 , 85, 1 2 7 , 1 9 4 7 , 3 3 1 3 , 4 687. Впрочем, Д Л Я чисел

данного вида существует более эффективный алгоритм.

Пример 5.8. Составим список всех натуральных л^5000, для которых число 2я4-л2 является простым. Для этого можно ввести в блокнот следующую программу.

М[п_]=2Лп+пЛ2;Do[ If[PrimeQ[M[n]],P r i n t [ n , , {n, 5000} ]

Вначале определена функция, вычисляющая число, а затем записан цикл, в кото­ ром проверяется простота ее значений. Будут выведены следующие числа: 1, 3, 9,

15, 21, 33, 2007, 2127, 3759.

Упражнение 5.1. Составьте список всех натуральных л^5000, для которых число

Т - 7 является простым.

Решение. Достаточно ввести в блокнот следующую программу.

М7 [nJ =2Лп-7;Do[ If[PrimeQ[М7[n]],Print[n,","]], {n, 5000} ]

В результате выполнения этой программы будут выведены следующие числа: 1,

2, 39, 715, 1983, 2319, 2499, 3775.

Упражнение 5.2. Найдите все простые числа, записываемые не более чем N единица­ ми. Иными словами, составьте список всех натуральных л^УУ, для которых является простым число, состоящее из л единиц. Рассмотрите случай N = 5000.

Решение. Достаточно ввести в блокнот следующую программу.

Mill[п_] = (10Лп-1)/9;Do[ If[PrimeQ[Mill[n]],Print[n,","]] , {n, 5000} ]

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

Mill[п_]=(10Ап-1)/9;

Do[ If[PrimeQ[n], If[PrimeQ[Mill[n]],Print[n, ", "]]] , {n, 5000} ]

В результате счета по этой программе будут выведены следующие числа: 2, 19,

23, 317, 1031.

Упражнение 5.3. Составьте список всех натуральных л<УУ,для которых является про­

стым число вида 10я +1 = 1000............... 00001 (п— 1 нулей в середине), состоя­

щее из л+1 цифр. Рассмотрите случай N = 131071 = 217-1.

Решение. Такие числа могут быть простыми лишь в том случае, если л является степенью двойки, т.е. если п - 2*. (При нечетных л, все такие числа делятся, напри­ мер, на сумму оснований, т.е. на 11.) Учитывая это, цикл можно вести лишь по пока­ зателям степеней двойки. Печатать нужно лишь те степени двойки, при которых рас­ сматриваемое число оказывается простым. Предельное значение, при котором можно

остановить цикл, равно наибольшему к, при котором 2k£N. Однако нужно учесть случай к = 0. Тогда программа будет выглядеть так.

М10001[п_] = ( Ю Л (2Ап) +1) ;Do [ If [PrimeQ [М10001 [n] ],Print [2Лп, ", "] ], (n, 0, 16} ]

В результате счета по этой программе будет выведено только два числа: 1, 2.

Упражнение 5.4. Найдите номера простых чисел Фибоначчи, не превышающие N. Иными словами, нужно составить список всех натуральных л^УУ, для которых число Фибоначчи F„ является простым. Рассмотрите случай N= 25 000.

Решение. Такие числа могут быть простыми лишь в том случае, если л является простым числом или л = 4. Поэтому цикл можно вести лишь по простым числам, учитывая, конечно, исключение л = 4. Печатать нужно лишь те л, при которых число Фибоначчи F„ оказывается простым. Вот как может выглядеть программа.

nl= 25000; Do[ If[n==4 ||

PrimeQ[n], I f[P rim eQ [F ib o n a cci[n ]] , P r i n t [ n , " , " ] ] ] , {n, nl} ]

В результате прогона этой программы будут выведены только следующие числа: з,

4, 5, 7, 11, 13, 17, 2 3 , 29, 43, 47, 83, 1 3 1 , 1 3 7 , 3 5 9 , 4 3 1 , 4 3 3 , 44.9, 5 0 9 , 5 6 9 , 5 7 1 , 2 9 7 1 , 4 7 2 3 , 5 3 8 7 , 9 3 1 1 , 9 6 7 7 , 1 4 4 3 1 .

Как видите, таких чисел совсем немного. В 1963 году наибольшим известным из этих чисел было только 47, которому отвечало всего лишь десятизначное число Фибо­ наччи.

Упражнение 5.5. Среди факториалов есть только одно простое число: 2 = 2!. Най­ дите все такие натуральные л, не превышающие N, что я!—1 — простое. Иными слова­ ми, нужно составить список всех натуральных n<N, для которых число л!—1 является простым. Рассмотрите случай N = 1 000.

Решение. Вот как может выглядеть программа.

n l = 1 0 0 0 ; D o [ I f [ P r i m e Q [ n ! 1 ] , P r i n t [ n , " , " ] ] , {n, n l } ]

Казалось бы, ничего необычного, однако обратите внимание на пробел между зна­ ком минус - и единицей 1. Если вы его не введете, программа будет синтаксически верной, но п! и - 1 просто перемножатся, и вы фактически будете искать простые числа среди факториалов.

В результате прогона этой программы будут выведены следующие числа: 3, 4, б,

7, 12, 14, 30, 32, 33, 3 8 , 94, 1 66, 3 2 4 , 3 7 9 , 4 6 9 , 5 4 6 , 974.

Упражнение 5.6. Найдите все такие натуральные п, не превышающие N, что п!+1 - простое. Иными словами, нужно составить список всех натуральных rt^N, для которых число п\+1 является простым. Рассмотрите случай N = 1 000.

Решение. Вот как может выглядеть программа.

n l = 1000; D o [ I f [ P r i m e Q [ n ! + 1 ] , P r i n t [ n , " , " ] ] , {n, n l } ]

В результате прогона этой программы будут выведены следующие числа: 1, 2, 3,

11, 2 7 , 37, 41, 73, 7 7, 1 1 6 , 1 54, 3 2 0 , 3 4 0 , 3 9 9 , 4 2 7 , 872.

Как видите, таких чисел совсем немного.

Множество простых чисел Primes и предикат х е Primes

В системе Mathematica имеется также множество (область) простых чисел P r im e s . Его также можно использовать для проверки простоты числа. Нужно просто прове­ рить, принадлежит ли число этому множеству. Убедимся, например, что число 1234567 составное.

1 2 3 4 5 6 7 6 P r im e s F a l s e

Доказательство (или опровержение) простоты заданного числа

Иногда нужно не только знать, простое или составное данное число, но и иметь доказательство (или опровержение) его простоты. Конечно, система Mathematica не пишет развернутый текст такого доказательства (или опровержения), но она может выдать систему чисел, доказывающую (или опровергающую) простоту заданного чис­ ла. Такая система чисел называется свидетельством, или сертификатом. Что может быть сертификатом? В принципе это зависит от “внутренней кухни” той системы, ко­ торая генерирует сертификат. В случае составного числа можно указать, например,

его нетривиальный делитель. При составном числе п можно также указать такое а, для которого не выполняется сравнение ап ]=l(modn). Система Mathematica для уста­

новления простоты числа использует теорию эллиптических кривых. Основанный на ней алгоритм, придуманный Аткином (Atkin), Голдвассером (Goldwasser) и Кильяном (Kilian), является в настоящее время наилучшим, если не принимать во внимание квантовых компьютеров, пока еще не реализованных. Этот алгоритм подробно описан в статье Atkin А. О. L. and Morain F. Elliptic Curves and Primality Proving (Mathematics of Computation, 1993, pp. 29~68). Однако on довольно сложен, и в настоящее время даже не все студенты-математики изучают его (как и теорию эллиптических кривых). По­ этому пользуются им чаще всего профессионалы. Тем не менее в отдельных случаях такой сертификат вполне понятен и для школьника. Вот пример. Вызвав функцию

PrimeQCertificate [ 3 8 3 7 5 2 3 ] , получим сертификат [ 2 , 3 8 3 7 5 2 2 , 3 8 3 7 5 2 3 } , ко­ торый показывает, что 23837522 (mod3837523) не равно 1. (Сертификаты, опровергающие

простоту, легко распознать: они всегда состоят из трех чисел.)

Функции PreviousPrime и NextPrime

ислучайные простые числа

Впакете теории чисел (загружается по команде «NumberTheory 'NumberTheoryFunctions ) имеются две чрезвычайно полезные функции, значениями которых яв­ ляются простые числа.

Наибольшее простое число, меньшее л, — PreviousPrime[n]

Функция PreviousPrime [п] генерирует наибольшее простое число, меньшее п. Если п не больше 2, будет сгенерировано отрицательное простое число.

PreviousPrim e [ 1 ]

-2

P re v io u sP rim e[2] -2

PreviousPrim e [ -7 2 ]

-73

P rev io u sP rim e [1000] . 997

Функция PreviousPrime[n] работает относительно быстро даже для большого аргумента.

PreviousPrime[2А1 2 8 ] //Timing

{0. S e c o n d , 3 4 0 2 8 2 3 6 6 9 2 0 9 3 8 4 6 3 4 6 3 3 7 4 6 0 7 4 3 1 7 6 8 2 1 1 2 9 7 }

PreviousPrime[2А2 5 6 ] //Timing

[0.031 Second,

1 1 5 7 9 2 0 8 9 2 3 7 3 1 6 1 9 5 4 2 3 5 7 0 9 8 5 0 0 8 6 8 7 9 0 7 8 5 3 2 6 9 9 8 4 6 6 5 6 4 0 5 6 4 0 3 9 4 5 7 5 8 4 0 0 7 9 1 3 1 29639747}

PreviousPrime[2A1 0 0 0 ] //Timing

[1.891 Second,

1 0 7 1 5 0 8 6 0 7 1 8 6 2 6 7 3 2 0 9 4 8 4 2 5 0 4 9 0 6 0 0 0 1 8 1 0 5 6 1 4 0 4 8 1 1 7 0 5 5 3 3 6 0 7 4 4 3 7 5 0 3 8 8 3 7 0 3 5 1

0 5 1 1 2 4 9 3 6 1 2 2 4 9 3 1 9 8 3 7 8 8 1 5 6 9 5 8 5 8 1 2 7 5 9 4 6 7 2 9 1 7 5 5 3 1 4 6 8 2 5 1 8 7 1 4 5 2 8 5 6 9 2 3 1 4 0 4 3 5

9 8 4 5 7 7 5 7 4 6 9 8 5 7 4 8 0 3 9 3 4 5 6 7 7 7 4 8 2 4 2 3 0 9 8 5 4 2 1 0 7 4 6 0 5 0 6 2 3 7 1 1 4 1 8 7 7 9 5 4 1 8 2 1 5 3 0 4 6 4

7 4 9 8 3 5 8 1 9 4 1 2 6 7 3 9 8 7 6 7 5 5 9 1 6 5 5 4 3 9 4 6 0 7 7 0 6 2 9 1 4 5 7 1 1 9 6 4 7 7 6 8 6 5 4 2 1 6 7 6 6 0 4 2 9 8 3 1 6 5 2 6 2 4 3 8 6 8 3 7 2 0 5 6 6 8 0 6 8 1 3 1 }

nl= 25000; Do[ If[n==4 ||

PrimeQ[n], If[P rim eQ [F ib o n a cci[n ]] , P r i n t [ n , " ," ]]] , {n, nl} ]

В результате прогона этой программы будут выведены только следующие числа: 3,

4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 44.9,

509, 569, 571,2971,4723,5387,9311, 9677,14431.

Как видите, таких чисел совсем немного. В 1963 году наибольшим известным из этих чисел было только 47, которому отвечало всего лишь десятизначное число Фибо­ наччи.

Упражнение 5.5. Среди факториалов есть только одно простое число: 2 = 2!. Най­ дите все такие натуральные я, не превышающие УУ, что я!—1 — простое. Иными слова­ ми, нужно составить список всех натуральных я^УУ, для которых число я!—1 является простым. Рассмотрите случай УУ= 1 000.

Решение. Вот как может выглядеть программа.

nl= 1000; Do[If[PrimeQ[n! 1],Print[n,","]], {n, nl} ]

Казалось бы, ничего необычного, однако обратите внимание на пробел между зна­ ком минус - и единицей 1. Если вы его не введете, программа будет синтаксически верной, но п! и -1 просто перемножатся, и вы фактически будете искать простые числа среди факториалов.

В результате прогона этой программы будут выведены следующие числа: 3, 4, 6,

7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974.

Упражнение 5.6. Найдите все такие натуральные п, не превышающие УУ, что п!+1 — простое. Иными словами, нужно составить список всех натуральных я^УУ, для которых число я!+1 является простым. Рассмотрите случай УУ= 1 000.

Решение. Вот как может выглядеть программа.

nl= 1000; Do[If[PrimeQ[n ! + 1],Print[n,","]], (n, nl} ]

В результате прогона этой программы будут выведены следующие числа: 1, 2, 3,

11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872.

Как видите, таких чисел совсем немного.

Множество простых чисел Primes и предикат х е Primes

В системе Mathematica имеется также множество (область) простых чисел P r i m e s . Его также можно использовать для проверки простоты числа. Нужно просто прове­ рить, принадлежит ли число этому множеству. Убедимся, например, что число 1234567 составное.

12345676 Primes

False

Доказательство (или опровержение) простоты заданного числа

Иногда нужно не только знать, простое или составное данное число, но и иметь доказательство (или опровержение) его простоты. Конечно, система Mathematica не пишет развернутый текст такого доказательства (или опровержения), но она может выдать систему чисел, доказывающую (или опровергающую) простоту заданного ч и с ­ ла. Такая система чисел называется свидетельством, или сертификатом. Что может быть сертификатом? В принципе это зависит от “внутренней кухни” той системы, ко­ торая генерирует сертификат. В случае составного числа можно указать, например,