Обозначим через $p_n$ $(n+1)$-е в порядке возрастания простое число: $p_0=2$, $p_1=3$, $p_2=5$, $p_3=7$, $p_4=11$, $p_5=13$ и т. д.
Широко распространено мнение, что не существует формулы, выражающей $p_n$
через $n$ при помощи арифметических операций. Оказывается, стоит только
добавить к арифметическим операциям функции «факториал»
($n!=1\cdot2\cdot\ldots\cdot n$; $0!=1$), «целую часть»
(см. с. 43)
и простенькую «логическую» функцию sg (читается «сигнум» — «знак»
по-латыни):
$$
\text{sg}(n)=\begin{cases}
1,&\text{если}~n\gt0,\\ 0,&\text{если}~n\le0,
\end{cases}
$$
как такую формулу уже можно написать (здесь $E(x)$ — «целая часть» числа
$x$):
$$
p_n=\sum\limits_{m=0}^{n^2+1}\text{sg}\left(n+1-\sum\limits_{k=2}^m
\left(((k-1)!)^2-k\cdot E\left(\dfrac{((k-1)!)^2}k\right)\right)\right).
$$
Аналогичную формулу прислал в редакцию московский десятиклассник
В. Гугнин.
Беда в том, что от подобных формул мало толку. Во-первых, вычисление по ним — не короче вычисления при помощи алгоритма «решето Эратосфена»
(«Квант», 1973, № 4,
с. 72 и 1974, № 1,
с. 77). Во-вторых, при их помощи затруднительно исследовать
«поведение» множества простых чисел «на бесконечности» (т. е. при $n\to\infty$) или, как говорят математики, «асимптотическое поведение»
множества простых чисел.
Тем не менее, по-видимому, приведённая формула удовлетворит потребность
некоторой части читателей «Кванта».
Как доказать предложенную формулу? В теории чисел через $\pi(m)$
обозначается число простых чисел, не превосходящих $m$. Легко сообразить,
что $$
\text{sg}(n+1-\pi(m))=\begin{cases}
1,&\text{если}~m\lt p_n,\\ 0,&\text{если}~m\ge p_n.
\end{cases}
$$
Пусть теперь $\mu$ — произвольная «оценка сверху» для $p_n$, т. е. такая
функция, что при всех $n$ имеем $p_n\le\mu(n)$. Тогда
$$
\textstyle p_n=\sum\limits_{m=0}^{\mu(n)}\text{sg}(n+1-\pi(m)).
$$
Пусть далее $\chi$ — характеристическая функция множества простых
чисел, т. е. такая функция, что $$
\chi(k)=\begin{cases}
1,&\text{если}~k~\text{— простое число},\\
0,&\text{если}~k~\text{— составное число.}
\end{cases}
$$
Очевидно,
$$
\textstyle\pi(m)=\sum\limits_{k=2}^m\chi(k).
$$
Тогда
$$
\textstyle p_n=\sum\limits_{m=0}^{\mu(n)}\text{sg}\left(n+1-\sum\limits_{k=2}^m
\chi(k)\right).\tag1
$$
Чтобы из формулы (1) получить конкретную формулу, надо подставить в неё какие-нибудь выражения для функций $\chi$ и $\mu$.
Наша формула как раз и получается из формулы (1) при $\mu(n)=n^2+1$ (в
теории чисел доказано, что $p_n\le n^2+1$ для всех $n$) и $$
\chi(k)=((k-1)!)^2-k\cdot E\left(\dfrac{((k-1)!)^2}k\right).\tag2
$$
Формула (2) получается при, помощи теоремы Вильсона: если $k$ —
простое число, то $(k-1)!+1$ делится на $k$.
