= (О й min А: S л) [{к +1) > л).

Эта функция представляет собой "целочисленный квадратный корень", который для обобщенности равен О при л < О.

24. л = {-л<39<л)(л = ).

Это предикат "d является делителем л", в соответствии с которым О О, но -i(01 л) при л/0.

25. n + d = if лйО then (-л2пип<л)(0<3г<-1)(л = + г)

else {nUTrmq<-n)[-\d\ + \u3r<0){n = qd + r).

Это формула для отсекающего целочислеьшого деления. Для d=0 формула произвольно дает результат л +1.

26. гет(л,) = л-(л-!-) .

Это обычная функция получения остатка при делении. Если гет(л,) имеет ненулевое значение, его знак равен знаку числителя л. Если d = 0, остаток равен п.

27. isprime(л) = л S 2 &-,(2 < 3d <л- л).

28. я(л) = isprime(i) (количество простых чисел, не превосходящих л).

29. р„ =[\<тшакй2"){п{к) = п).

30. ехропеп1(р,л) = (0<пипл:йл)-,(р"л).

Это формула показателя степени простого множителя р данного числа л > 1, 31.Для л>0:

2"=П2, 2=П2, 2=П2 ИТ.Д.

Значение этого выражения есть наименьшее х в диапазоне от от до л, такое, что предикат для него оказывается истинным, либо т в случае пустого диапазона, либо л +1, если предикат ложен для всего (непустого) диапазона. Эта операция называется "ограниченной минимизацией" и является весьма мощным инструментом при разработке новых формульных функций. Вычисление такой минимизации, представляющей собой тип функциональной инверсии, предложено Гудштейном (Goodstein) [23].

Таким образом, класс ф(Ч)мульных функций весьма больпюй. Тем не менее он ограничен, как минимум, следующей теоремой.

Теорема. Если f- формульная функция, то существует константа к, такая, что где количество двоек равно к.

Эту теорему можно доказать, показав, что каждое из правил 1-5 сохраняет справедливость теоремы. Например, если /(Зс) = с (правило 1), то для некоторого h

f{x)<2]h,

где имеется h двоек. Таким образом.

/(х)<2-

/1 + 2,

потому что тах(х,,...,х„)>0.

Для f{x) = x, (правило 2) /(Г)тах(х,,...,л:„), так что теоремавыполняется с =0. Рассмотрим правило 3. Пусть

Тогда очевидно, что

к, и в{х)2-

к,<.

f{x)±g{x)2-2- тах(*„2)<

<2

»(И1-+»1)

гаях.{к,к2) + \.

Аналогично можно показать, что теорема выполняется для f[x,y) = xy.

Доказательства того, что правила 4 и 5 сохраняют справедливость теоремы, утомительны и сложны, так что здесь они не приводятся. Из теоремы следует, что функция

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

Для тех, кто интересуется теорией рекурснвных функций, укажем, что (4) представляет собой примитивную рекурсию. Кроме того, можно легко показать непосредственно из определения примитивной рекурсии, что формульные функции представляют собой примитивную рекурсию. Таким образом, класс формульных функций представляет собой

16.4. ФОРМУЛЫ ДЛЯ ДРУГИХ СЛОЖНЫХ ФУНКЦИЙ

истинное подмножество примитивных ре10рсивных функций. Заинтересовавшемуся этим вопросом читателю можно посоветовать обратиться к [9].

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

Впрочем, после знакомства с приведенными функциями для простых чисел они перестают казаться столь интересными, и вопрос об "интересных" формулах для простых чисел остается открытым. Например, в [53] приведена удивительная теорема Миллса (W.H. Mills) о том, что существует 0, такое, что выражение

дает простые числа для всех л S1. На самом деле имеется бесконечное число таких значений (например, 1.3063778838+ и 1.453 750 862 548 3+). Кроме того, нет ничего выдающегося и в числе 3: теорема остается верна, если заменить тройку любым большим ее целым числом (разумеется, для других значений 0). Более того, тройку можно заменить даже двойкой, если справедливо не доказанное до сих пор утверждение, что между

л и (п+1)" всегда имеется по крайней мере одно простое число. Более того... Впрочем,

заинтересовавшийся читатель сам найдет в [13, 53] множество формул такого типа.