Близнецы

Изучая распределение простых чисел, мы узнали, что интервалы, состоящие из составных чисел, могут быть сколь угодно длинными. Однако встречаются и очень короткие интервалы, ограниченные простыми числами. Простые числа 2 и 3 следуют друг за другом, не пропуская между собой ни одного составного числа. Но это, конечно, исключение, больше нигде не встречающееся в натуральном ряду. Но зато немало встречается таких пар простых чисел, между которыми стоит только одно составное число (четное, естественно). Простые числа, разность которых равна 2, называются близнецами. Честно говоря, это наименьшая возможная разность между нечетными простыми числами. (Потому что все простые числа, за исключением 2, нечетны!) Вот как определяется функция, которая отыскивает все пары близнецов среди первых т простых чисел.
TwinPrimes[m_]:= Module[{s=Prime[Range[m]]}, {#,#+2}&/@Extract[s,Position[Dropfs,1]- Drop[s,-l],2]]]
Вот, например, список пар близнецов среди первой тысячи простых чисел.

Число простых чисел не превосходящих х (функция PrimePi[x])

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

Согласитесь, изучив все тонкости искусства составления таблиц простых чисел, было бы нелогично пренебречь искусством составления таблиц на основе уже созданных. Почему бы, имея полную (значит, бесконечную!) таблицу простых чисел, не поинтересоваться, сколько чисел в этой таблице не превосходят данного числа х. Иными словами, определить число простых чисел, не превосходящих х. Это число в учебниках теории чисел обозначается л(х). Функция п(х) привлекала внимание уже античных математиков. Евклид, например, установил, что она неограниченно возрастает с ростом аргумента. Изучением этой функции занимались почти все великие математики Прошлого, ее исследовали Лежандр, Чебышев, Риман, Адамар, Валле-Пуссен, Чудаков, Виноградов, Коробов, Литлвуд, Сельберг, Эрдеш, Ингам, Прахар, Пан Чен-тонг, Чен-ин-рун, Титчмарш, Мейссель, Рогель, Чипола, Мертенс, Гаусс, Бертран, Вейль, Линник, Бомбьери...

В системе Mathematica эта функция называется PrimePi. Система Mathematica может вычислить ее значения практически в мгновение ока... Правда, не все.

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

Иногда нужно не только знать, простое или составное данное число, но и иметь доказательство (или опровержение) его простоты. Конечно, система Mathematica не пишет развернутый текст такого доказательства (или опровержения), но она может выдать систему чисел, доказывающую (или опровергающую) простоту заданного числа. Такая система чисел называется свидетельством, или сертификатом. Что может быть сертификатом? В принципе это зависит от "внутренней кухни" той системы, которая генерирует сертификат. В случае составного числа можно указать, например, его нетривиальный делитель. При составном числе n можно также указать такое а, для которого не выполняется сравнение an-1 =1(modn). Система Mathematica для установления простоты числа использует теорию эллиптических кривых. Основанный на ней алгоритм, придуманный Аткином (Atkin), Голдвассером (Goldwasser) и Кильяном (Kilian), является в настоящее время наилучшим, если не принимать во внимание квантовых компьютеров, пока еще не реализованных. Этот алгоритм подробно описан в статье Atkin А. О. L. and Morain F. Elliptic Curves and Primality Proving (Mathematics of Computation, 1993, pp. 29-68). Однако он довольно сложен, и в настоящее время даже не все студенты-математики изучают его (как и теорию эллиптических кривых). Поэтому пользуются им чаще всего профессионалы. Тем не менее в отдельных случаях такой сертификат вполне понятен и для школьника. Вот пример. Вызвав функцию PrimeQCertificate[3837523], получим сертификат {2, 3837522, 3837523}, который показывает, что 238"522(mod3837523) не равно 1. (Сертификаты, опровергающие простоту, легко распознать: они всегда состоят из трех чисел.)

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

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

Функция Prime[n] — nе простое число рn

Функция Prime[n] — n-е простое число рn

В предыдущей главе, разлагая числа на простые множители, мы опустили вопрос о том, как составляются таблицы простых чисел. Тем не менее этот вопрос интересовал еще древних греков, и Эратосфен изобрел решето, пользоваться которым умеет каждый пятиклассник. Однако обычно незачем заниматься столь утомительным занятием: в необходимых случаях система Mathematica изготовляет это самое решето и трясет его сколько надо. Пользователю же предоставляется функция Prime [n], которая возвращает n-е простое число рn. Поэтому, чтобы построить таблицу первых 100 простых чисел, достаточно одной команды.

Функция PrimeQ

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

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

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

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

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

PrimeQ[1] False PrimeQ[-1] False

Кроме того, как и следует ожидать, она применима и к целым отрицательным числам, причем PrimeQ[-n] = PrimeQ[n]. Более того, она применима к целым гауссовым числам, и если ее аргумент — число с ненулевой мнимой частью, она осуществляет проверку на простоту именно в области гауссовых чисел. Однако если вы хотите в кольце гауссовых чисел проверить на простоту число с нулевой мнимой частью, придется указать опцию GaussianIntegers->True.
PrimeQ[5] True PrimeQ[5+0 I] True PrimeQ[5,Gaussianlntegers-XTrue] False
Пример 5.1. Составим таблицу нескольких первых чисел Ферма с указанием их простоты. Вот что надо ввести в блокнот.

Количество простых чисел на открытом слева отрезке (а b]

Количество простых чисел на открытом слева отрезке (а, b]

С помощью функции PrimePi несложно подсчитать и количество простых чисел на открытом слева отрезке (а, b]. Помните только, что если вы пользуетесь выражением k(b)-n(а), т.е. выражением PrimePi [b] -PrimePi [a], то в случае простоты простое число b будет посчитано, а простое число а — нет. Иными словами, подсчет осуществляется на открытом слева отрезке (а, b]. А что, если нужно посчитать простые числа на замкнутом с обоих концов отрезке [а, b}1 Ничего сложного: в качестве аргумента можно взять не а, а несколько меньшее число, ведь аргументом функции PrimePi может быть любое вещественное положительное число. Давайте посчитаем, например, количество простых чисел в 1-й, 2-й, ... , 20-й сотне миллионов натуральных чисел. Вот как это можно сделать.
delta=100000000; PrimePiAB[delta_Integer?Positive,xk_Integer?Positive]:= Block[{k=0, x=delta, kt=0 }, While[x<=xk, {kt=PrimePi[x]; Print[x,":",kt,":",kt-k]; k=kt; x=x+delta}]] PrimePiAB[delta,10 delta]
Полученные результаты удобно представить в виде таблицы .

В приведенной выше программе мы воспользовались тем, что интервалы примыкают друг к другу. Однако так бывает не всегда. Иногда нужно подсчитать количество простых чисел в интервалах заданной длины, причем начала интервалов расположены на числовой оси так, что конец очередного интервала не совпадает с началом следующего. Подсчитаем, например, количество простых чисел в интервалах длиной 150000, причем пусть начинаются эти интервалы в точках х= 106, 107, ... , 1014. Для этого случая пригодится следующая функция.
DeltaPi[x_,delta_]:= Block[{xk=x+delta,k=PrimePi[xk]}, Print[x,"-",xk,":",k-PrimePi[x]]]
С помощью этой функции нетрудно написать и нужную нам программу.

delta=150000;

Do[DeltaPi[10^n,delta],{n,6,14)]

Результаты отформатированы в виде таблицы.

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

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

1234567€Primes False

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

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

Функция PreviousPrime [n] генерирует наибольшее простое число, меньшее n. Если n не больше 2, будет сгенерировано отрицательное простое число.
PreviousPrime[1] -2 PreviousPrime[2 ] -2 PreviousPrime[-72] -73 PreviousPrime[1ООО] 997
Функция PreviousPrime [n] работает относительно быстро даже для большого аргумента.

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

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

Функция NextPrime[n] генерирует наименьшее простое число, большее n.
NextPrime[-1000] -997 NextPrime[-l] 2 NextPrimeflOOO] 1009 NextPrime[1009] 1013
Функция NextPrime[n] работает относительно быстро даже для большого аргумента.

Пифагоровы треугольники у которых

Пифагоровы треугольники, у которых длины двух сторон выражаются простыми числами

Как известно, треугольники, у которых длины двух сторон выражаются целыми числами, называются пифагоровыми. Хорошо известно, что длина ни одной из сторон пифагорового треугольника не может быть равна 2. Поэтому у пифагоровых треугольников длины сторон могут выражаться только нечетными простыми числами. А потому длина хотя бы одной из сторон пифагорова треугольника должна быть четной (по теореме Пифагора) и потому выражается составным числом. (Составным потому, что четным, отличным от 2.) Боле того, несложно доказать, что если р и q — длины сторон пифагорова треугольника, выражающиеся простыми числами, то р2 = 2q -1.

И наоборот, если существуют такие простые числа р и q, что р2 = 2q - 1, то в прямоугольном треугольнике с гипотенузой q и катетом р второй катет равен vq2 - р2 = q -1 ,

и потому такой треугольник будет пифагоровым. Для нахождения пифагоровых треугольников, у которых длины двух сторон выражаются простыми числами, можно применить функции PrimeQ и NextPrime. Область поиска ограничим теми треугольниками, у которых меньший катет р не превосходит заданного числа п. Достаточно найти длину меньшего катета р и длину гипотенузы q, поскольку длина второго катета на единицу меньше длины гипотенузы: q-1

Поиск отрезков натурального ряда

Поиск отрезков натурального ряда, состоящих только из составных чисел

За одним-единственным исключением pn =2, р2 = 3, числа рn и рn+1 не являются смежными в натуральном ряду. Еще Евклид знал, что существуют сколь угодно длинные отрезки натурального ряда, целиком состоящие из составных чисел. Как же найти отрезок натурального ряда, целиком состоящий из составных чисел? Для этого полезно определить следующую функцию.

Простые числа близкие к числам определенного вида

Простые числа, близкие к числам определенного вида

В ряде областей науки и техники, например в теории кодирования, важно знать простые числа, близкие к числам определенного вида (чаще всего к степеням таких оснований, как 2, 3 и 10). Вне сомнения, их можно было бы найти в обычных таблицах простых чисел. Однако таблицы нужного размера не могли бы поместиться даже в многотомных изданиях. Поэтому существуют специальные таблицы, в которых приводятся только простые числа, близкие, например, к 2n, 3n и 10n.

Но составить такие таблицы для достаточно больших n довольно трудно, и, несмотря на компактность, такие таблицы зачастую весьма неполны. С помощью системы Mathematica несложно составить такие таблицы самостоятельно. Допустим, таблица должна содержать десять наибольших простых чисел, предшествующих N, и десять простых чисел, следующих за N. Можно ограничиться случаем достаточно больших N, например N>1000, поскольку при меньших N вопрос решается с помощью таблиц простых чисел, помещаемых обычно в учебниках для пятиклассников.

Давайте попытаемся составить нужную нам программу, например, для степеней 10. Чтобы результаты выглядели наглядно, нужно предусмотреть их преобразование в таблицу с помощью текстового процессора, например, Word. Поэтому необходимо предусмотреть такой формат результатов, который было бы легко отформатировать (преобразовать в таблицу). Для этого можно предусмотреть двоеточие : в качества разделителя колонок и два двоеточия : : в качестве разделителя строк таблицы. Вот как может выглядеть программа.

Хотя каждый математик знает, ох,

Резюме

Хотя каждый математик знает, ох, как это непросто, нужно признать, что система Mathematica дружит с простыми числами. В ней есть функции, проверяющие, является ли число простым; функция, генерирующая n-е простое число; функция, генерирующая следующее простое число; функция, генерирующая предыдущее простое число; а также знаменитая функция n(х), подсчитывающая количество простых чисел, не превосходящих заданного числа х. Конечно, реализовать все эти функции весьма непросто, и применяя их, нужно учитывать ограничения на их аргументы. Но как бы то ни было, в системе Mathematica они реализованы на современном уровне, с учетом совсем недавно доказанных теорем и новых методов.

Случайное простое число в заданном

Случайное простое число в заданном интервале — Random[Prime, {n, m}]

Иногда нужно сгенерировать какое-нибудь случайное простое число, лежащее в заданном интервале. Для этого используется конструкция Random [Prime, {n, m}]. Вот несколько примеров ее использования.
Random[Prime,{10^6,10^12}] 837590772197 Random[Prime,{10^6+0.5,10^12}] 924457361921
Конечно, если в указанном интервале простых чисел нет, будет сгенерировано предупреждение. Вот пример некорректного вызова.

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

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

Мехматовский фольклор

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

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

Мерсенн, XVII в.

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

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