Функция распределения простых чисел

В математике функция распределения простых чисел, или пи-функция [math]\displaystyle{ \pi (x) }[/math], — это функция, равная числу простых чисел, меньших либо равных действительному числу x.^[1]^[2] Она обозначается [math]\displaystyle{ \pi(x) }[/math] (это никак не связано с числом пи).

Значения пи-функции для первых 60 натуральных чисел

История

Большой интерес в теории чисел представляет скорость роста пи-функции.^[3]^[4] В конце XVIII столетия Гауссом и Лежандром было выдвинуто предположение, что пи-функция оценивается как

[math]\displaystyle{ \frac{x}{\ln x} }[/math]

в смысле, что

[math]\displaystyle{ \lim\limits_{x\to +\infty}\frac{\pi(x)}{x/\ln x}=1. }[/math]

Это утверждение — теорема о распределении простых чисел. Оно эквивалентно утверждению

[math]\displaystyle{ \lim\limits_{x\to +\infty}\frac{\pi(x)}{\operatorname{li}(x)}=1 }[/math]

где [math]\displaystyle{ \operatorname{li} }[/math] — это интегральный логарифм. Теорема о простых числах впервые была доказана в 1896 Жаком Адамаром и независимо Валле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.

Точнее рост [math]\displaystyle{ \pi(x) }[/math] сейчас описывается как

[math]\displaystyle{ \pi(x) = \operatorname{li}(x) + O\bigl(xe^{-\sqrt{\ln x}/15}\bigr) }[/math]

где [math]\displaystyle{ O }[/math] обозначает O большое. Когда x не сильно велико [math]\displaystyle{ \operatorname{li}(x) }[/math] больше, чем [math]\displaystyle{ \pi(x) }[/math], однако разность [math]\displaystyle{ \pi (x)-\operatorname{li}(x) }[/math] меняет свой знак бесконечное число раз, наименьшее натуральное число, для которого происходит смена знака называется числом Скьюза.

Доказательства теоремы о простых числах, не использующие дзета-функцию или комплексный анализ, были найдены в 1948 году Атле Сельбергом и Паулем Эрдёшом (большей частью независимо).^[5]

Таблицы для пи-функции, x / ln x и li(x)

В следующей таблице показан рост функций [math]\displaystyle{ \pi(x),\frac{x}{\ln x},\operatorname{li}(x) }[/math] по степеням 10^[3]^[6]^[7]^[8].

x	π(x)	π(x) − x / ln x	li(x) − π(x)	x / π(x)	π(x)/x (доля простых чисел)
10	4	−0,3	2,2	2,500	40 %
10²	25	3,3	5,1	4,000	25 %
10³	168	23	10	5,952	16,8 %
10⁴	1 229	143	17	8,137	12,3 %
10⁵	9 592	906	38	10,425	9,59 %
10⁶	78 498	6 116	130	12,740	7,85 %
10⁷	664 579	44 158	339	15,047	6,65 %
10⁸	5 761 455	332 774	754	17,357	5,76 %
10⁹	50 847 534	2 592 592	1 701	19,667	5,08 %
10¹⁰	455 052 511	20 758 029	3 104	21,975	4,55 %
10¹¹	4 118 054 813	169 923 159	11 588	24,283	4,12 %
10¹²	37 607 912 018	1 416 705 193	38 263	26,590	3,76 %
10¹³	346 065 536 839	11 992 858 452	108 971	28,896	3,46 %
10¹⁴	3 204 941 750 802	102 838 308 636	314 890	31,202	3,20 %
10¹⁵	29 844 570 422 669	891 604 962 452	1 052 619	33,507	2,98 %
10¹⁶	279 238 341 033 925	7 804 289 844 393	3 214 632	35,812	2,79 %
10¹⁷	2 623 557 157 654 233	68 883 734 693 281	7 956 589	38,116	2,62 %
10¹⁸	24 739 954 287 740 860	612 483 070 893 536	21 949 555	40,420	2,47 %
10¹⁹	234 057 667 276 344 607	5 481 624 169 369 960	99 877 775	42,725	2,34 %
10²⁰	2 220 819 602 560 918 840	49 347 193 044 659 701	222 744 644	45,028	2,22 %
10²¹	21 127 269 486 018 731 928	446 579 871 578 168 707	597 394 254	47,332	2,11 %
10²²	201 467 286 689 315 906 290	4 060 704 006 019 620 994	1 932 355 208	49,636	2,01 %
10²³	1 925 320 391 606 803 968 923	37 083 513 766 578 631 309	7 250 186 216	51,939	1,92 %
10²⁴	18 435 599 767 349 200 867 866	339 996 354 713 708 049 069	17 146 907 278	54,243	1,84 %
10²⁵	176 846 309 399 143 769 411 680	3 128 516 637 843 038 351 228	55 160 980 939	56,546	1,77 %
10²⁶	1 699 246 750 872 437 141 327 603	28 883 358 936 853 188 823 261	155 891 678 121	58,850	1,70 %
10²⁷	16 352 460 426 841 680 446 427 399	267 479 615 610 131 274 163 365	508 666 658 006	61,153	1,64 %

В OEIS первая колонка значений [math]\displaystyle{ \pi(x) }[/math] — это последовательность A006880, [math]\displaystyle{ \pi(x)-\left\lfloor\frac{x}{\ln x}+0{,}5\right\rfloor }[/math] — это последовательность A057835, а [math]\displaystyle{ \lfloor\operatorname{li}(x)+0{,}5\rfloor-\pi(x) }[/math] — это последовательность A057752.

Алгоритмы вычисления пи-функции

Простой способ найти [math]\displaystyle{ \pi(x) }[/math], если [math]\displaystyle{ x }[/math] не очень велико, — это использование решета Эратосфена выдающего простые, не превосходящие [math]\displaystyle{ x }[/math] и подсчитать их.

Более продуманный способ вычисления [math]\displaystyle{ \pi(x) }[/math] был дан Лежандром: дан [math]\displaystyle{ x }[/math], если [math]\displaystyle{ p_1,p_2,\ldots,p_k }[/math] — различные простые числа, то число целых чисел, не превосходящих [math]\displaystyle{ x }[/math] и не делящихся на все [math]\displaystyle{ p_i }[/math] равно

[math]\displaystyle{ \lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i\lt j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i\lt j\lt k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots }[/math]

(где [math]\displaystyle{ \lfloor\cdots\rfloor }[/math] обозначает целую часть). Следовательно, полученное число равно

[math]\displaystyle{ \pi(x)-\pi\left(\sqrt{x}\right)+1 }[/math]

если числа [math]\displaystyle{ p_1, p_2,\ldots,p_k }[/math] — это все простые числа, не превосходящие [math]\displaystyle{ \sqrt{x} }[/math].

В 1870—1885 годах в серии статей Эрнст Майссель описал (и использовал) практический комбинаторный способ вычисления [math]\displaystyle{ \pi(x) }[/math]. Пусть [math]\displaystyle{ p_1,p_2,\ldots,p_n }[/math] — первые [math]\displaystyle{ n }[/math] простых, обозначим [math]\displaystyle{ \Phi(m,n) }[/math] число натуральных чисел, не превосходящих [math]\displaystyle{ m }[/math], которые не делятся ни на одно [math]\displaystyle{ p_i }[/math]. Тогда

[math]\displaystyle{ \Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right) }[/math]

Возьмем натуральное [math]\displaystyle{ m }[/math], если [math]\displaystyle{ n=\pi\left(\sqrt[3]{m}\right) }[/math] и если [math]\displaystyle{ \mu=\pi\left(\sqrt{m}\right)-n }[/math], то

[math]\displaystyle{ \pi(m)=\Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu}{2}-1-\sum_{k=1}^\mu\pi\left(\frac{m}{p_{n+k}}\right) }[/math]

Используя этот подход, Майссель вычислил [math]\displaystyle{ \pi(x) }[/math] для [math]\displaystyle{ x=5\cdot 10^5;10^6;10^7;10^8 }[/math].

В 1959 году Деррик Генри Лемер расширил и упростил метод Майсселя. Определим, для действительного [math]\displaystyle{ m }[/math] и для натуральных [math]\displaystyle{ n,k }[/math] величину [math]\displaystyle{ P_k(m,n) }[/math] как число чисел, не превосходящих m имеющих ровно k простых множителей, причем все они превосходят [math]\displaystyle{ p_n }[/math]. Кроме того, положим [math]\displaystyle{ P_0(m,n)=1 }[/math]. Тогда

[math]\displaystyle{ \Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n) }[/math]

где сумма явно всегда имеет конечное число ненулевых слагаемых. Пусть [math]\displaystyle{ y }[/math] — целое, такое, что [math]\displaystyle{ \sqrt[3]{m}\leqslant y\leqslant\sqrt{m} }[/math], и положим [math]\displaystyle{ n=\pi(y) }[/math]. Тогда [math]\displaystyle{ P_1(m,n)=\pi(m)-n }[/math] и [math]\displaystyle{ P_k(m,n)=0 }[/math] при [math]\displaystyle{ k\geqslant 3 }[/math]. Следовательно

[math]\displaystyle{ \pi(m)=\Phi(m,n)+n-1-P_2(m,n) }[/math]

Вычисление [math]\displaystyle{ P_2(m,n) }[/math] может быть получено следующим способом:

[math]\displaystyle{ P_2(m,n)=\sum_{y\lt p\leqslant\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right) }[/math]

С другой стороны, вычисление [math]\displaystyle{ \Phi(m,n) }[/math] может быть выполнено с помощью следующих правил:

[math]\displaystyle{ \Phi(m,0)=\lfloor m\rfloor }[/math]
[math]\displaystyle{ \Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right) }[/math]

Используя этот метод и IBM 701, Лемер смог вычислить [math]\displaystyle{ \pi\left(10^{10}\right) }[/math].

Дальнейшие усовершенствования этого метода были сделаны Lagarias, Miller, Odlyzko, Deleglise и Rivat.^[9]

Китайский математик Hwang Cheng использовал следующие тождества:^[10]

[math]\displaystyle{ e^{(a-1)\Theta}f(x)=f(ax), }[/math]

[math]\displaystyle{ J(x)=\sum_{n=1}^{\infty}\frac{\pi(x^{1/n})}{n} }[/math]

и, полагая [math]\displaystyle{ x=e^t }[/math], выполняя преобразование Лапласа обеих частей и применяя сумму геометрической прогрессии с [math]\displaystyle{ e^{n\Theta} }[/math], получил выражение:

[math]\displaystyle{ \frac{1}{2{\pi}i}\int_{c-i\infty}^{c+i\infty}g(s)t^{s}\,ds = \pi(t) }[/math]

[math]\displaystyle{ \frac{\ln \zeta(s)}{s}=(1-e^{\Theta(s)})^{-1}g(s) }[/math]

[math]\displaystyle{ \Theta(s)=s\frac{d}{ds} }[/math]

Другие функции, подсчитывающие простые числа

Другие функции, подсчитывающие простые числа, также используются, поскольку с ними удобнее работать. Одна из них — функция Римана, часто обозначаемая как [math]\displaystyle{ \Pi_0(x) }[/math] или [math]\displaystyle{ J_0(x) }[/math]. Она испытывает прыжок на 1/n для степеней простых [math]\displaystyle{ p^n }[/math], причем в точке прыжка [math]\displaystyle{ x }[/math] её значение равно полусумме значений на обеих сторонах от [math]\displaystyle{ x }[/math]. Эти дополнительные детали нужны для того, чтобы она могла быть определена обратным преобразованием Меллина. Формально, мы определим [math]\displaystyle{ \Pi_0(x) }[/math] как

[math]\displaystyle{ \Pi_0(x) = \frac12 \bigg(\sum_{p^n \lt x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg) }[/math]

где p простое.

Мы также можем записать

[math]\displaystyle{ \Pi_0(x) = \sum\limits_{n=2}^x \frac{\Lambda(n)}{\ln n} - \frac12 \frac{\Lambda(x)}{\ln x} = \sum_{n=1}^\infty \frac1n \pi_0(\sqrt[n]{x}) }[/math]

где [math]\displaystyle{ \Lambda(n) }[/math] — функция Мангольдта и

[math]\displaystyle{ \pi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2. }[/math]

Формула обращения Мёбиуса дает

[math]\displaystyle{ \pi_{0}(x) = \sum_{n=1}^\infty \frac{\mu(n)}n \Pi_0(\sqrt[n]{x}) }[/math]

Используя известное соотношение между логарифмом дзета-функции Римана и функцией Мангольдта [math]\displaystyle{ \Lambda }[/math], и используя формулу Перрона мы получим

[math]\displaystyle{ \ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s-1}\,dx }[/math]

Функция Римана имеет производящую функцию

[math]\displaystyle{ \sum_{n=1}^\infty \Pi_0(n)x^n = \sum_{a=2}^\infty \frac{x^{a}}{1-x} - \frac{1}{2}\sum_{a=2}^\infty \sum_{b=2}^\infty \frac{x^{ab}}{1-x} + \frac{1}{3}\sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty \frac{x^{abc}}{1 -x} - \frac{1}{4}\sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty \sum_{d=2}^\infty \frac{x^{abcd}}{1-x} + \cdots }[/math]

Функции Чебышёва — это функции, подсчитывающие степени простых чисел [math]\displaystyle{ p^n }[/math] с весом [math]\displaystyle{ \ln p }[/math]:

[math]\displaystyle{ \theta(x)=\sum_{p\leqslant x}\ln p }[/math]

[math]\displaystyle{ \psi(x) = \sum_{p^n\leqslant x} \ln p = \sum_{n=1}^\infty \theta(\sqrt[n]{x}) = \sum_{n\leqslant x}\Lambda(n). }[/math]

Формулы для функций, подсчитывающих простые числа

Формулы для функций, подсчитывающих простые числа, бывают двух видов: арифметические формулы и аналитические формулы. Аналитические формулы для таких функций были впервые использованы для доказательства теоремы о простых числах. Они происходят от работ Римана и Мангольдта и в общем известны как явные формулы.^[11]

Существует следующее выражение для [math]\displaystyle{ \psi }[/math]-функции Чебышёва:

[math]\displaystyle{ \psi_0(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \ln 2\pi - \frac12 \ln(1-x^{-2}) }[/math]

где

[math]\displaystyle{ \psi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\psi(x-\varepsilon)+\psi(x+\varepsilon)}2. }[/math]

Здесь [math]\displaystyle{ \rho }[/math] пробегает нули дзета-функции в критической полосе, где действительная часть [math]\displaystyle{ \rho }[/math] лежит между нулем и единицей. Формула верна для всех [math]\displaystyle{ x\gt 1 }[/math]. Ряд по корням сходится условно, и может быть взят в порядке абсолютного значения возрастания мнимой части корней. Заметим, что аналогичная сумма по тривиальным корням дает последнее слагаемое в формуле.

Для [math]\displaystyle{ \scriptstyle\Pi_0(x) }[/math] мы имеем следующую сложную формулу

[math]\displaystyle{ \Pi_0(x) = \operatorname{li}(x) - \sum_{\rho}\operatorname{li}(x^{\rho}) - \ln 2 + \int_x^\infty \frac{dt}{t(t^2-1) \ln t}. }[/math]

Опять же, формула верна для всех [math]\displaystyle{ x\gt 1 }[/math], где [math]\displaystyle{ \rho }[/math] — нетривиальные нули зета-функции, упорядоченные по их абсолютному значению, и, снова, последний интеграл берется со знаком «минус» и является такой же суммой, но по тривиальным нулям. Выражение [math]\displaystyle{ \operatorname{li}(x^{\rho}) }[/math] во втором члене может быть рассмотренно как [math]\displaystyle{ \operatorname{Ei}(\rho\ln x) }[/math], где [math]\displaystyle{ \operatorname{Ei} }[/math] — это аналитическое продолжение интегральной показательной функции на комплексную плоскость с ветвью, вырезанной вдоль прямой [math]\displaystyle{ x\lt 0 }[/math].

Таким образом, формула обращения Мёбиуса дает нам^[12]

[math]\displaystyle{ \pi_{0}(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^{\rho})-\frac{1}{\ln x}+\frac{1}{\pi}\mathop{\mathrm{arctg}} \frac{\pi}{\ln x} }[/math]

верное для [math]\displaystyle{ x\gt 1 }[/math], где

[math]\displaystyle{ \operatorname{R}(x)=\sum_{n=1}^{\infty}\frac{\mu (n)}{n}\operatorname{li}(x^{1/n})=1+\sum_{k=1}^\infty \frac{(\ln x)^k}{k! k \zeta(k+1)} }[/math]

называется R-функцией также в честь Римана.^[13] Последний ряд в ней известен как ряд Грама^[14] и сходится для всех [math]\displaystyle{ x\gt 0 }[/math].

Сумма по нетривиальным нулям дзета-функции в формуле для [math]\displaystyle{ \pi_0(x) }[/math] описывает флуктуации [math]\displaystyle{ \pi_0(x) }[/math], в то время как остальные слагаемые дают гладкую часть пи-функции,^[15] поэтому мы можем использовать

[math]\displaystyle{ \operatorname{R}(x) - \frac{1}{\ln x} + \frac{1}{\pi}\mathop{\mathrm{arctg}}\frac{\pi}{\ln x} }[/math]

как наилучшее приближение для [math]\displaystyle{ \pi(x) }[/math] для [math]\displaystyle{ x\gt 1 }[/math].

Амплитуда «шумной» части эвристически оценивается как [math]\displaystyle{ \sqrt x/\ln x }[/math], поэтому флуктуации в распределении простых могут быть явно представлены [math]\displaystyle{ \Delta }[/math]-функцией:

[math]\displaystyle{ \Delta(x) = \left( \pi_0(x) - \operatorname{R}(x) + \frac{1}{\ln x} - \frac{1}{\pi}\mathop{\mathrm{arctg}}\frac{\pi}{\ln x} \right) \frac{\ln x}{\sqrt x}. }[/math]

Обширные таблицы значений [math]\displaystyle{ \Delta(x) }[/math] доступны здесь.^[7]

Неравенства

Здесь выписаны некоторые неравенства для [math]\displaystyle{ \pi (x) }[/math].

[math]\displaystyle{ \frac{x}{\ln x}\lt \pi(x)\lt 1{,}25506\cdot \frac{x}{\ln x} \qquad x \geqslant 17. }[/math]

Левое неравенство выполняется при [math]\displaystyle{ x \geqslant 17 }[/math], а правое — при [math]\displaystyle{ x\gt 1. }[/math]^[16]

Неравенства для [math]\displaystyle{ n }[/math]-го простого числа [math]\displaystyle{ p_n }[/math]:

[math]\displaystyle{ n\ln n+n\ln\ln n -3/2\cdot n\lt p_n\lt n\ln n +n\ln\ln n, \ n\geqslant 6. }[/math]

Левое неравенство верно при [math]\displaystyle{ n \geqslant 2 }[/math], а правое — при [math]\displaystyle{ n \geqslant 6 }[/math].

Имеет место следующая асимптотика для [math]\displaystyle{ n }[/math]-го простого числа [math]\displaystyle{ p_n }[/math]:

[math]\displaystyle{ p_n = n\ln n\left(1+\frac{\ln\ln n-1}{\ln n}+\frac{\ln\ln n-2}{\ln ^2 n}+\frac{-1/2\ln ^2\ln n+3\ln\ln n -11/2}{\ln^3 n}+O\left(\frac{\ln^3\ln n}{\ln^4 n}\right)\right) }[/math]

Гипотеза Римана

Гипотеза Римана эквивалентна более точной границе ошибки приближения [math]\displaystyle{ \pi(x) }[/math] интегральным логарифмом, а отсюда и более регулярному распределению простых чисел

[math]\displaystyle{ \pi(x) = \operatorname{li}(x) + O(\sqrt{x} \ln x). }[/math]

В частности,^[17]

[math]\displaystyle{ |\pi(x) - \operatorname{li}(x)| \lt \frac{1}{8\pi} \sqrt{x} \, \ln x, \qquad x \geqslant 2657. }[/math]

См. также

Примечания

↑ Bach, Eric; Shallit, Jeffrey. Section 8.8 // Algorithmic Number Theory (неопр.). — MIT Press, 1996. — Т. 1. — С. 234. — ISBN 0-262-02405-5.
↑ Weisstein, Eric W. Prime Counting Function (англ.) на сайте Wolfram MathWorld.
↑ ^3,0 ^3,1 How many primes are there? (неопр.). Chris K. Caldwell. Дата обращения: 2 декабря 2008. Архивировано 20 сентября 2012 года.
↑ Dickson, Leonard Eugene^[англ.]. History of the Theory of Numbers I: Divisibility and Primality (англ.). — Dover Publications, 2005. — ISBN 0-486-44232-2.
↑ K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory (англ.). — Second. — Springer, 1998. — ISBN 0-387-97329-X.
↑ Tables of values of pi(x) and of pi2(x) (неопр.). Tomas Oliveira e Silva. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.
↑ ^7,0 ^7,1 Values of π(x) and Δ(x) for various x's (неопр.). Andrey V. Kulsha. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.
↑ A table of values of pi(x) (неопр.). Xavier Gourdon, Pascal Sebah, Patrick Demichel. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.
↑ Computing ?(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method (неопр.). Marc Deleglise and Joel Rivat, Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.
↑ Hwang H., Cheng. Demarches de la Geometrie et des Nombres de l'Universite du Bordeaux, Prime Magic conference.
↑ Titchmarsh, E.C. The Theory of Functions, 2nd ed (англ.). — Oxford University Press, 1960.
↑ Riesel, Hans^[англ.]; Gohl, Gunnar. Some calculations related to Riemann's prime number formula (англ.) // Mathematics of Computation^[англ.] : journal. — American Mathematical Society, 1970. — Vol. 24, no. 112. — P. 969—983. — ISSN 0025-5718. — doi:10.2307/2004630. — JSTOR 2004630.
↑ Weisstein, Eric W. Riemann Prime Counting Function (англ.) на сайте Wolfram MathWorld.
↑ Weisstein, Eric W. Gram Series (англ.) на сайте Wolfram MathWorld.
↑ The encoding of the prime distribution by the zeta zeros (неопр.). Matthew Watkins. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.
↑ Rosser, J. Barkley^[англ.]; Schoenfeld, Lowell. Approximate formulas for some functions of prime numbers (англ.) // Illinois J. Math. : journal. — 1962. — Vol. 6. — P. 64—94. — ISSN 0019-2082. Архивировано 28 февраля 2019 года.
↑ Lowell Schoenfeld. Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II (англ.) // Mathematics of Computation^[англ.] : journal. — American Mathematical Society, 1976. — Vol. 30, no. 134. — P. 337—360. — ISSN 0025-5718. — doi:10.2307/2005976. — JSTOR 2005976.

Литература

К. Прахар. Распределение простых чисел. — Мир, 1967.
В. И. Зенкин. Распределение простых чисел. Элементарные методы. Калининград, 2008.

Ссылки

Chris Caldwell, The Nth Prime Page at The Prime Pages.

[Bach-1] Bach, Eric; Shallit, Jeffrey. Section 8.8 // Algorithmic Number Theory (неопр.). — MIT Press, 1996. — Т. 1. — С. 234. — ISBN 0-262-02405-5.

[mathworld_pcf-2] Weisstein, Eric W. Prime Counting Function (англ.) на сайте Wolfram MathWorld.

[Caldwell-3] 3,0 ^3,1 How many primes are there? (неопр.). Chris K. Caldwell. Дата обращения: 2 декабря 2008. Архивировано 20 сентября 2012 года.

[Dickson-4] Dickson, Leonard Eugene^[англ.]. History of the Theory of Numbers I: Divisibility and Primality (англ.). — Dover Publications, 2005. — ISBN 0-486-44232-2.

[Ireland-5] K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory (англ.). — Second. — Springer, 1998. — ISBN 0-387-97329-X.

[Silva-6] Tables of values of pi(x) and of pi2(x) (неопр.). Tomas Oliveira e Silva. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.

[Kulsha-7] 7,0 ^7,1 Values of π(x) and Δ(x) for various x's (неопр.). Andrey V. Kulsha. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.

[Gourdon-8] A table of values of pi(x) (неопр.). Xavier Gourdon, Pascal Sebah, Patrick Demichel. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.

[pix_comp-9] Computing ?(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method (неопр.). Marc Deleglise and Joel Rivat, Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.

[Cheng-10] Hwang H., Cheng. Demarches de la Geometrie et des Nombres de l'Universite du Bordeaux, Prime Magic conference.

[Titchmarsh-11] Titchmarsh, E.C. The Theory of Functions, 2nd ed (англ.). — Oxford University Press, 1960.

[12] Riesel, Hans^[англ.]; Gohl, Gunnar. Some calculations related to Riemann's prime number formula (англ.) // Mathematics of Computation^[англ.] : journal. — American Mathematical Society, 1970. — Vol. 24, no. 112. — P. 969—983. — ISSN 0025-5718. — doi:10.2307/2004630. — JSTOR 2004630.

[mathworld_r-13] Weisstein, Eric W. Riemann Prime Counting Function (англ.) на сайте Wolfram MathWorld.

[mathworld_gram-14] Weisstein, Eric W. Gram Series (англ.) на сайте Wolfram MathWorld.

[Watkins-15] The encoding of the prime distribution by the zeta zeros (неопр.). Matthew Watkins. Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.

[16] Rosser, J. Barkley^[англ.]; Schoenfeld, Lowell. Approximate formulas for some functions of prime numbers (англ.) // Illinois J. Math. : journal. — 1962. — Vol. 6. — P. 64—94. — ISSN 0019-2082. Архивировано 28 февраля 2019 года.

[17] Lowell Schoenfeld. Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II (англ.) // Mathematics of Computation^[англ.] : journal. — American Mathematical Society, 1976. — Vol. 30, no. 134. — P. 337—360. — ISSN 0025-5718. — doi:10.2307/2005976. — JSTOR 2005976.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]