Доказано, что для nSl имеется, как минимум, одно простое число между п и 2п. Следовательно, количество простых чисел, не превышающих 2", по меньшей мере равно п, т.е. л(2")йп. Таким образом, предикат я(и)<п для in>2" равен О, так что верхний

предел суммирования можно заменить на 2".

Виллане использовал более искусную замену для выражения-предиката. Пусть

Щх,у) =

длях = 0,1,2...;у = 1,2,...

Тогда, если х<у, то 1йу/{1 + х)йу, так что +х) ulfy <2. Кроме того, если

х>у,то 0<у/{1 + х)<1, так что Ойу/{1+х)<1. Применяя функцию наибольшего целого, не превосходящего заданное число ("пол"), получим

Щх,у) = \

- [о, х>у,

так что LT{x,y) представляет собой предикат х<у (для дг и у из указанных диапазонов). Подставив полученное выражение в (3), получим

2"

,..,.LT(.H.»).,.2[ .

Дальнейшая подстановка уравнения (2) для выражения л(т) через F{x) и уравнения (1) для F{x) дает нам формулу, приведенную в начале этого раздела.

Вторая формула

Виллане дал еще одну формулу для п-го простого числа:

p„=£wF(«)

7-И"Ы

Здесь Fan- функции, использовавшиеся в первой формуле. Таким образом, mF(m) равно т, если т- простое число или единица, и О, если т- составное число.

Третий множитель представляет собой предикат л(т) = п. Все члены суммы равны О, кроме одного, равного и-му простому числу. Например:

р„ =М-0 + 2-1-0+3-1-0+4 0-0 + 5-1-0+6 0-0 + 7-М + +8 0-1 + 9 0-1 + 10 0 1 + 1М0 + ... + 160-0 = 7.

Третья формула

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

Это термин автора книги, а не Вилланса.

целое + -, если д:-простое число,

[целое, если д: - составное число или 1. Первая часть следует из того, что

{{х-Щ J{x-l)M)-{{x-iy.-l) 1 X х х

и (д:-1)!+1 делится на д: в соответствии с теоремой Вильсона. Таким образом, предикат "д: - простое число" для д:й2 задается следующим образом:

Н{х) = -

. 1 л sin- -

Из этого следует

п{т) = Н{х), т = 2,3,...

Эту формулу нельзя преобразовать в формулу для р„ методами, использованными в первых двух формулах Вилланса, так как в них применяется функция "пол". Вместо этого Виллане предложил следующую формулу* для предиката д: < у при д:, у > 1:

ЬТ(д:,у) = 5ш

Таким образом, если д:<у, то е = д:(д:-1)...(0)(-1)...(д:-(у-1)) = 0, так что ЬТ(д:,у) = 5ш(л/2) = 1. Если х>у, произведение не включает О, так что е>1 и LT (д:, у) = sin ((л/2) • (чегиое число)) = О .

Наконец, как и в первой формуле Вилланса,

р„=2 + £ьТ(л(т),л).

Объединив все вместе, получим следующую "жуть":

Л =2 +sin

* Мы немного упростили эту формулу. • 16.2. ФОРМУЛЫ ВИЛЛАНСА

Четвертая формула

После этого Виллане приводит еще одну формулу, которая выражает простое число р„+1 через р„:

/».1=1+/„+£П/(л+Л

(=1 м

где / (х) - предикат "х - составное число", д: S 2, т.е.

В качестве альтернативы можно использовать соотнощение f(x) = l-H(x), что позволит

избежать применения функщ1И "пол".

Рассмотрим пример работы этой формулы для р„ = 7 . Тогда

Л«=1 + 7 + /(8) + /(8)/(9) + /(8)/(9)/(10) +

+/(8)/(9)/(10)/(11) + ... + /(8)/(9).../(14) = = 1 + 7 + 1 + Ы + 111 + 11-10 + ...1-Ы0101 = 11.

16.3. Формула Вормелла

Вормелл (СР. Wormell) [63] усоверщенствовал формулу Вилланса, убрав из нее как тригонометрические функции, так и функцию "пол". Вычисления по формуле Вормелла в принципе могуг быть проведены с помощью простой компьютерной программы с использованием только целочисленной арифметики. Ее вывод не использует теорему Вильсона. Вормелл начал с того, что для х2

положительное целое, если х - простое число, О, если X - составное число.

Таким образом, количество простых чисел, не превосходящих т, задается соотнощением

потому что под знаком суммы находится предикат "х - простое число". Заметим, что для л > 1, а S О

о, если а < л,

положительное целое, если а>п.

Повторяя описанный выще прием, находим, что предикат д < л можно выразить следующим образом:

Поскольку