ГЛАВА 16

ФОРМУЛЫ для ПРОСТЫХ ЧИСЕЛ

16.1. Введение

Как и все молодые студенты, я в свое время был очарован простыми числами и пытался найти формулу для их поиска. Я не знал точно, какие операции должны использоваться в этой "формуле", и даже не очень представлял себе, какую именно функцию я ищу: функцию, которая по заданному и будет возвращать л-е простое число, или по заданному простому числу будет находить следующее простое число, или будет просто давать простые числа, хотя и не все из них. Сейчас, наперекор всем этим неоднозначностям, я хочу рассмотреть, что же все же известно нам по этой проблеме? В результате вы узнаете, что формулы для простых чисел существуют, но все они не очень удовлетворительны.

Начнем наше рассмотрение с краткой истории вопроса.

В 1640 году Ферма предположил, что формула

F„=2"+l

всегда дает простые числа, и числа этого вида получили название "чисел Ферма". Предположение Ферма справедливо для и от О до 4, но в 1732 году Эйлер обнаружил, что

=2+1 = 641-6700417.

(Мы уже имели дело с этими множителями, когда рассматривали вопросы деления на константу на 32-битовом компьютере.) Затем в 1880 году Ландри показал, что

F,=2* +1 = 274177-67 280421310721.

В настоящее время известно, что F„ - составные числа для многих больших значений и, в частности для и от 7 до 16 включительно. В настоящее время неизвестно ни одно значение л>4, для которого число Ферма было бы простым [33]. Увы, гипотеза оказалась слишком поспешной...

Почему же Ферма использовал двойное возведение в степень? Он знал, что если т имеет нечетный множитель, отличный от 1, то 2" +1 - составное число. Если т = аЬ, где b нечетно и не равно 1, то

2"* +1 = (2 +l)(2°f- 2°(-> +2"<-" -... + 1).

Зная это. Ферма заинтересовался числами 2"" +1, такими, где т не имеет ни одного нечетного множителя, отличного от 1, т.е. ,п = 2". Он испробовал несколько значений п и

убедился, что они дают простые числа 2 +1.

Практически все согласны, что полином вполне можно считать "формулой". В 1772 году Эйлером был опфыт удивительный полином

/(л) = л-+л+41.

Справедошвостн ради надо заметить, что это единственная известная ошибочная гипотеза Ферма [61].

обладающий тем свойством, что он дает простые числа для всех и от О до 39. Этот результат может быть расширен. Так как

/(-л) = л-и + 41 = /(п-1),

/(-л) дает простые числа для каждого и из диапазона от 1 до 40, т.е. /(л) дает простые числа для всех и от -1 до -40. Таким образом, полином

/(л-40) = (л-40) +(л-40) + 41 = л -79Л + 1601

дает простые числа для всех и от О до 79. (Однако эстетическая привлекательность формулы при этом теряется, так как она дает повторяющиеся и немонотонные результаты - для

,1=0,1.....79 формула дает числа 1601,1523,1447,.... 43,41,41, 43,.... 1447,1523,1601.)

Несмотря на всю пртлекательность полинома, открытого Эйлером, известно, что не существует полиномиальной формулы /(л), которая давала бы простое число для каждого и (не считая тривиального случая константного полинома типа /(л) = 5). Более того, справедлива следующая теорема [33].

Теорема. Если /(л) = Р(п,2",3",...,А:°) представляет собой полином с целочисленными коэффициентами от своих аргументов и f(n)-><x> при п-><х>, то f[n) является составным значением для бесконечного множества значений п.

Следовательно, формула типа л 2° + 2л + 2л + 5 должна давать бесконечное количество составных чисел. С другой стороны, теорема ничего не говорит о формулах, содержащих члены наподобие 2", л" или и!.

Формула для п-го целого простого числа может быть получена при помощи функции получения максимального целого, не превосходящего данное число ("пол"), н магического значения

а = 0.203005000700011000013...

Число а в десятичной системе счисления представляет собой первое простое число, записанное в первой позиции после десятичной точки, второе простое число, записанное в следующих двух позициях, третье, записанное в следующих трех позициях и т.д. При этом для очередного простого числа всегда найдется достаточно свободного места, так как /7„ < 10°. Не доказывая этого, просто заметим: поскольку известно, что между и и 2п (л>2) всегда есть простое число, значит, между л и Юл оно есть наверняка, а отсюда следует, что р„ < 10". Формула для и-го простого числа выглядит следующим образом:

где было использовано соотношение

л +л

Например:

р, = [lOaJ -10 [Юа J = 203005 - 203000 = 5.

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

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

16.2. Формулы Вилланса

Первая формула

Виллане (С.Р. Willans) дал следуюшую формулу для и-го простого числа [62]:

Vlgcos

Вывод этой формулы начинается с теоремы Вильсона, которая гласит, что р является простым или равно 1 тогда и только тогда, когда (р -1)! = -1 (mod р). Таким образом.

будет целым для простого х (или д:= 1) и дробным для всех составных х. Следовательно,

fl, д: простое или 1,

F(x) =

cos Tl--•-

[О, х составное.

Таким образом, если п{т) обозначает количество простых чисел, не превышающих т, то

n{m) = -\+±F{x). (2)

Заметим, что я (;?„) = л, а кроме того,

л(т)<л для т<р,, н л(т)>л для т>р„.

Таким образом, количество значений w от 1 до <», для которых л(т) < л, равно р„-1, т.е.

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

Поскольку у нас есть формула для л(т), уравнение (3) представляет собой формулу

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

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

16.2. ФОРМУЛЫ ВИЛЛАНСА