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

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

Файл:PrimePi.svg

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

История

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

в смысле, что

<math>\lim\limits_{x\to +\infty}\frac{\pi(x)}{x/\ln x}=1.</math>

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

<math>\lim\limits_{x\to +\infty}\frac{\pi(x)}{\operatorname{li}(x)}=1</math>

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

Точнее рост <math>\pi(x)</math> сейчас описывается как

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

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

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

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

В следующей таблице показан рост функций <math>\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>\pi(x)</math> — это последовательность Шаблон:OEIS2C, <math>\pi(x)-\left\lfloor\frac{x}{\ln x}+0{,}5\right\rfloor</math> — это последовательность Шаблон:OEIS2C, а <math>\lfloor\operatorname{li}(x)+0{,}5\rfloor-\pi(x)</math> — это последовательность Шаблон:OEIS2C.

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

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

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

<math>\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots</math>

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

<math>\pi(x)-\pi\left(\sqrt{x}\right)+1</math>

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

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

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

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

<math>\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>\pi(x)</math> для <math>x=5\cdot 10^5;10^6;10^7;10^8</math>.

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

<math>\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n)</math>

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

Вычисление <math>P_2(m,n)</math> может быть получено следующим способом:

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

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

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

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

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

<math>e^{(a-1)\Theta}f(x)=f(ax),</math>

<math>J(x)=\sum_{n=1}^{\infty}\frac{\pi(x^{1/n})}{n}</math>

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

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

<math>\frac{\ln \zeta(s)}{s}=(1-e^{\Theta(s)})^{-1}g(s)</math>

<math>\Theta(s)=s\frac{d}{ds}</math>

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

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

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

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

<math>\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>\Lambda(n)</math> — функция Мангольдта и

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

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

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

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

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

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

<math>\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>p^n</math> с весом <math>\ln p</math>:

<math>\theta(x)=\sum_{p\leqslant x}\ln p</math>

<math>\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>\psi</math>-функции Чебышёва:

где

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

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

Для <math>\scriptstyle\Pi_0(x)</math> мы имеем следующую сложную формулу

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

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

<math>\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>x>1</math>, где

<math>\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>x>0</math>.

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

<math>\operatorname{R}(x) - \frac{1}{\ln x} + \frac{1}{\pi}\mathop{\mathrm{arctg}}\frac{\pi}{\ln x}</math>

как наилучшее приближение для <math>\pi(x)</math> для <math>x>1</math>.

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

<math>\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>\Delta(x)</math> доступны здесь.^[7]

Неравенства

Здесь выписаны некоторые неравенства для <math>\pi (x)</math>.

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

Неравенства для <math>n</math>-го простого числа <math>p_n</math>:

Левое неравенство верно при <math>n \geqslant 2</math>, а правое — при <math>n \geqslant 6</math>.

Имеет место следующая асимптотика для <math>n</math>-го простого числа <math>p_n</math>:

<math> 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>

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

Шаблон:Main

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

<math>\pi(x) = \operatorname{li}(x) + O(\sqrt{x} \ln x).</math>

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

<math>|\pi(x) - \operatorname{li}(x)| < \frac{1}{8\pi} \sqrt{x} \, \ln x, \qquad x \geqslant 2657. </math>

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

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

[Bach-1] Шаблон:Книга

[mathworld_pcf-2] Шаблон:MathWorld

[Caldwell-3] 3,0 ^3,1 Шаблон:Cite web

[Dickson-4] Шаблон:Книга

[Ireland-5] Шаблон:Книга

[Silva-6] Шаблон:Cite web

[Kulsha-7] 7,0 ^7,1 Шаблон:Cite web

[Gourdon-8] Шаблон:Cite web

[pix_comp-9] Шаблон:Cite web

[Cheng-10] Шаблон:Cite news

[Titchmarsh-11] Шаблон:Книга

[12] Шаблон:Статья

[mathworld_r-13] Шаблон:MathWorld

[mathworld_gram-14] Шаблон:MathWorld

[Watkins-15] Шаблон:Cite web

[16] Шаблон:Статья

[17] Шаблон:Статья

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.