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

«Π(x)» перенаправляется сюда. О варианте гамма-функции см. Гамма-функция § Функция Пи .

В математике функция подсчета простых чисел — это функция, подсчитывающая количество простых чисел, меньших или равных некоторому действительному числу x . Он обозначается π ( x ) (не связан с числом π ).

Значения π ( n ) для первых 60 положительных целых чисел

Темпы роста

Основная статья: Теорема о простых числах

Большой интерес в теории чисел представляет скорость роста функции подсчета простых чисел. , что оно предположили В конце XVIII века Гаусс и Лежандр составляет примерно

$${\frac {x}{\log(x)}}$$

где log — натуральный логарифм в том смысле, что

$$\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.$$

Это утверждение является теоремой о простых числах . Эквивалентное утверждение

$$\lim _{x\rightarrow \infty }{\frac {\pi (x)}{\operatorname {li} (x)}}=1$$

где li — логарифмическая интегральная функция. Теорема о простых числах была впервые доказана в 1896 году Жаком Адамаром и Шарлем де ла Валле Пуссеном независимо друг от друга с использованием свойств дзета-функции Римана , введенной Риманом доказательства теоремы о простых числах без использования дзета-функции или комплексного анализа. в 1859 году. Были найдены около 1948 года Атле Сельберг и Пол Эрдеш (по большей части независимо).

Более

В 1899 году де ла Валле Пуссен доказал, что

$$\pi (x)=\operatorname {li} (x)+O\left(xe^{-a{\sqrt {\log x}}}\right)\quad {\text{as }}x\to \infty$$

для некоторой положительной константы a . Здесь O (...) это большое O. обозначение —

более точные оценки π ( x ) Теперь известны . Например, в 2002 году Кевин Форд доказал, что

$$\pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-0.2098(\log x)^{3/5}(\log \log x)^{-1/5}\right)\right).$$

Мосингхофф и Труджиан доказали явная верхняя граница разницы между π ( x ) и li( x ) :

$${\bigl |}\pi (x)-\operatorname {li} (x){\bigr |}\leq 0.2593{\frac {x}{(\log x)^{3/4}}}\exp \left(-{\sqrt {\frac {\log x}{6.315}}}\right)\quad {\text{for }}x\geq 229.$$

Для значений x , которые не являются неоправданно большими, li( x ) больше π ( x ) . Однако известно, что π ( x ) − li( x ) меняет знак бесконечное число раз. Обсуждение этого вопроса см. в номере Скьюза .

Точная форма

Для x > 1 пусть π ₀ ( x ) = π ( x ) − 1/2 , π когда x — простое число, и π ₀ ( x ) = в ( x ) противном случае. Бернхард Риман в своей работе «О числе простых чисел, меньших заданной величины » доказал, π0 _что ( x ) равно

Явная формула Римана, использующая первые 200 нетривиальных нулей дзета-функции.

$$\pi _{0}(x)=\operatorname {R} (x)-\sum _{\rho }\operatorname {R} (x^{\rho }),$$

где

$$\operatorname {R} (x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\operatorname {li} \left(x^{1/n}\right),$$

µ ( n ) — функция Мёбиуса , li( x ) — логарифмическая интегральная функция , ρ индексирует каждый нуль дзета-функции Римана, а li( x ^{р / н} ) не оценивается с разрезом ветки , а вместо этого рассматривается как Ei( ρ / n log x ) , где Ei( x ) — экспоненциальный интеграл . Если собрать тривиальные нули и суммировать только по нетривиальным нулям ρ дзета-функции Римана, то π ₀ ( x ) можно аппроксимировать выражением

$$\pi _{0}(x)\approx \operatorname {R} (x)-\sum _{\rho }\operatorname {R} \left(x^{\rho }\right)-{\frac {1}{\log(x)}}+{\frac {1}{\pi }}\arctan {\frac {\pi }{\log(x)}}.$$

Гипотеза Римана предполагает, что каждый такой нетривиальный нуль лежит вдоль Re( s ) = 1 / 2 .

Таблица π ( x ) , x / log( x ) и li( x )

В таблице сравниваются точные значения π ( x ) с двумя приближениями x / log x и li ( x ) . Последний столбец, x / π ( x ) , представляет собой средний разрыв простых чисел ниже x .

х	π ( Икс )	π ( Икс ) - х / журнал( х )	li( Икс ) - π ( Икс )	х / журнал( х ) % ошибка	ли ( х ) % ошибка	Икс / π ( Икс )
10	4	0	2	8.22%	42.606%	2.500
10 2	25	3	5	14.06%	18.597%	4.000
10 3	168	23	10	14.85%	5.561%	5.952
10 4	1,229	143	17	12.37%	1.384%	8.137
10 5	9,592	906	38	9.91%	0.393%	10.425
10 6	78,498	6,116	130	8.11%	0.164%	12.739
10 7	664,579	44,158	339	6.87%	0.051%	15.047
10 8	5,761,455	332,774	754	5.94%	0.013%	17.357
10 9	50,847,534	2,592,592	1,701	5.23%	3.34 × 10 −3  %	19.667
10 10	455,052,511	20,758,029	3,104	4.66%	6.82 × 10 −4  %	21.975
10 11	4,118,054,813	169,923,159	11,588	4.21%	2.81 × 10 −4  %	24.283
10 12	37,607,912,018	1,416,705,193	38,263	3.83%	1.02 × 10 −4  %	26.590
10 13	346,065,536,839	11,992,858,452	108,971	3.52%	3.14 × 10 −5  %	28.896
10 14	3,204,941,750,802	102,838,308,636	314,890	3.26%	9.82 × 10 −6  %	31.202
10 15	29,844,570,422,669	891,604,962,452	1,052,619	3.03%	3.52 × 10 −6  %	33.507
10 16	279,238,341,033,925	7,804,289,844,393	3,214,632	2.83%	1.15 × 10 −6  %	35.812
10 17	2,623,557,157,654,233	68,883,734,693,928	7,956,589	2.66%	3.03 × 10 −7  %	38.116
10 18	24,739,954,287,740,860	612,483,070,893,536	21,949,555	2.51%	8.87 × 10 −8  %	40.420
10 19	234,057,667,276,344,607	5,481,624,169,369,961	99,877,775	2.36%	4.26 × 10 −8  %	42.725
10 20	2,220,819,602,560,918,840	49,347,193,044,659,702	222,744,644	2.24%	1.01 × 10 −8  %	45.028
10 21	21,127,269,486,018,731,928	446,579,871,578,168,707	597,394,254	2.13%	2.82 × 10 −9  %	47.332
10 22	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1,932,355,208	2.03%	9.59 × 10 −10  %	49.636
10 23	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	7,250,186,216	1.94%	3.76 × 10 −10  %	51.939
10 24	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	17,146,907,278	1.86%	9.31 × 10 −11  %	54.243
10 25	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	55,160,980,939	1.78%	3.21 × 10 −11  %	56.546
10 26	1,699,246,750,872,437,141,327,603	28,883,358,936,853,188,823,261	155,891,678,121	1.71%	9.17 × 10 −12  %	58.850
10 27	16,352,460,426,841,680,446,427,399	267,479,615,610,131,274,163,365	508,666,658,006	1.64%	3.11 × 10 −12  %	61.153
10 28	157,589,269,275,973,410,412,739,598	2,484,097,167,669,186,251,622,127	1,427,745,660,374	1.58%	9.05 × 10 −13  %	63.456
10 29	1,520,698,109,714,272,166,094,258,063	23,130,930,737,541,725,917,951,446	4,551,193,622,464	1.53%	2.99 × 10 −13  %	65.759

График, показывающий отношение функции подсчета простых чисел π ( x ) к двум ее аппроксимациям, x / log x и Li( x ) . По мере x увеличения (обратите внимание, что ось x логарифмическая), оба отношения стремятся к 1. Отношение для x / log x сходится сверху очень медленно, тогда как отношение для Li( x ) сходится быстрее снизу.

В Электронной энциклопедии целочисленных последовательностей столбец π ( x ) — это последовательность OEIS : A006880 , π ( x ) − x / log x — это последовательность OEIS : A057835 , а li( x ) − π ( x ) — это последовательность OEIS : A057752 .

Значение π (10 ²⁴ ) первоначально была вычислена Дж. Бюте, Дж. Франке , А. Йостом и Т. Кляйнъунгом в предположении гипотезы Римана . Позже это было безоговорочно подтверждено расчетами DJ Platt. Значение π (10 ²⁵ ) принадлежит Й. Бюте, Й. Франке , А. Йосту и Т. Кляйнъюнгу. Значение π (10 ²⁶ ) было рассчитано DB Staple. Все остальные предыдущие записи в этой таблице также были проверены в рамках этой работы.

Значения для 10 ²⁷ , 10 ²⁸ , и 10 ²⁹ были объявлены Дэвидом Боугом и Ким Валишем в 2015 году, 2020, и 2022 год, соответственно.

Алгоритмы вычисления π ( x )

Простой способ найти π ( x ) , если x не слишком велико, — это использовать решето Эратосфена, чтобы получить простые числа, меньшие или равные x , а затем посчитать их.

Более сложный способ нахождения π ( x ) принадлежит Лежандру (с использованием включения-исключения ): при заданном x , если p1 _или , p2 _, …, pn _{принципа} — различные простые числа, то количество целых чисел меньше равный x , который не делится ни на один p _​​i ,

$\lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots$

(где ⌊ x ⌋ обозначает функцию пола ). Следовательно, это число равно

$\pi (x)-\pi \left({\sqrt {x}}\right)+1$

когда числа p ₁ , p ₂ ,…, p _n являются простыми числами, меньшими или равными квадратному корню из x .

Алгоритм Мейселя-Лемера

Основная статья: алгоритм Мейселя – Лемера

В серии статей, опубликованных между 1870 и 1885 годами, Эрнст Мейсель описал (и использовал) практический комбинаторный способ вычисления π ( x ) : пусть p ₁ , p ₂ ,…, p _n — первые n простых чисел и обозначают Φ( m , n ) количество натуральных чисел не больше m , которые не делятся ни на одно из чисел для _pi любого i ≤ n . Затем

$\Phi (m,n)=\Phi (m,n-1)-\Phi \left({\frac {m}{p_{n}}},n-1\right).$

Учитывая натуральное число m , если n = π ( ³ √ м ), и если µ знак равно π ( √ м ) - п , то

$\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).$

Используя этот подход, Мейсель вычислил π ( x ) для x , равного 5 × 10 ⁵ , 10 ⁶ , 10 ⁷ , и 10 ⁸ .

В 1959 году Деррик Генри Лемер расширил и упростил метод Мейселя. Определите для действительных m и натуральных чисел n и k с P _k ( m , n ) как количество чисел, не превышающих m, ровно k простыми делителями, все из которых больше p _n . Кроме того, установите P ₀ ( m , n ) = 1 . Затем

$\Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n)$

где сумма на самом деле имеет лишь конечное число ненулевых членов. Пусть y обозначает целое число такое, что ³ √ m ≤ y ≤ √ m и положим n знак равно π ( y ) . Тогда п ₁ ( м , п ) знак равно π ( м ) - п и п _k ( м , п ) = 0, когда k ≥ 3 . Поэтому,

$\pi (m)=\Phi (m,n)+n-1-P_{2}(m,n)$

Вычисление P ₂ ( m , n ) можно получить таким образом:

$P_{2}(m,n)=\sum _{y<p\leq {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right)$

где сумма ведется по простым числам.

С другой стороны, вычисление Φ( m , n ) может быть выполнено с использованием следующих правил:

1. $\Phi (m,0)=\lfloor m\rfloor$
2. $\Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right)$

Используя свой метод и IBM 701 , Лемер смог вычислить правильное значение π (10 ⁹ ) и пропустил правильное значение π (10 ¹⁰ ) на 1.

Дальнейшие усовершенствования этого метода были внесены Лагариасом, Миллером, Одлызко, Делеглизом и Риватом.

чисел

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

подсчета простых

Функция подсчета простых чисел Римана обычно обозначается как Π ₀ ( x ) или J ₀ ( x ) . Он имеет прыжки 1 / n в степенях простых чисел p ^н и оно принимает значение на полпути между двумя сторонами на разрывах π ( x ) . Эта дополнительная деталь используется, поскольку функция затем может быть определена с помощью обратного преобразования Меллина .

Формально мы можем определить Π ₀ ( x ) как

$\Pi _{0}(x)={\frac {1}{2}}\left(\sum _{p^{n}<x}{\frac {1}{n}}+\sum _{p^{n}\leq x}{\frac {1}{n}}\right)\$

где переменная p в каждой сумме варьируется по всем простым числам в указанных пределах.

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

$\ \Pi _{0}(x)=\sum _{n=2}^{x}{\frac {\Lambda (n)}{\log n}}-{\frac {\Lambda (x)}{2\log x}}=\sum _{n=1}^{\infty }{\frac {1}{n}}\pi _{0}\left(x^{1/n}\right)$

где Λ — функция фон Мангольдта и

$\pi _{0}(x)=\lim _{\varepsilon \to 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.$

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

$\pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\ \Pi _{0}\left(x^{1/n}\right),$

где µ ( n ) – функция Мёбиуса .

Зная связь между логарифмом дзета-функции Римана и функцией фон Мангольдта Λ , и используя формулу Перрона, имеем

$\log \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s-1}\,\mathrm {d} x$

Функция Чебышева

Функция Чебышева взвешивает простые числа или степени простых чисел p ^н по журналу ( р ) :

${\begin{aligned}\theta (x)&=\sum _{p\leq x}\log p\\\psi (x)&=\sum _{p^{n}\leq x}\log p=\sum _{n=1}^{\infty }\theta \left(x^{1/n}\right)=\sum _{n\leq x}\Lambda (n).\end{aligned}}$

Для x ≥ 2 ,

$\vartheta (x)=\pi (x)\log x-\int _{2}^{x}{\frac {\pi (t)}{t}}\,\mathrm {d} t$

и

$\pi (x)={\frac {\vartheta (x)}{\log x}}+\int _{2}^{x}{\frac {\vartheta (t)}{t\log ^{2}(t)}}\mathrm {d} t.$

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

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

Имеем следующее выражение для второй функции Чебышева ψ :

$\psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\log 2\pi -{\frac {1}{2}}\log \left(1-x^{-2}\right),$

где

$\psi _{0}(x)=\lim _{\varepsilon \to 0}{\frac {\psi (x-\varepsilon )+\psi (x+\varepsilon )}{2}}.$

Здесь ρ — нули дзета-функции Римана в критической полосе, где действительная часть ρ находится между нулем и единицей. Формула действительна для значений x больше единицы, что является областью интереса. Сумма по корням условно сходится, и ее следует брать в порядке возрастания абсолютного значения мнимой части. Обратите внимание, что та же самая сумма по тривиальным корням дает последнее вычитаемое в формуле.

Для Π ₀ ( x ) имеем более сложную формулу

$\Pi _{0}(x)=\operatorname {li} (x)-\sum _{\rho }\operatorname {li} \left(x^{\rho }\right)-\log 2+\int _{x}^{\infty }{\frac {\mathrm {d} t}{t\left(t^{2}-1\right)\log t}}.$

Опять же, формула справедлива для x > 1 , а ρ — нетривиальные нули дзета-функции, упорядоченные по их абсолютному значению. Интеграл равен ряду по тривиальным нулям:

$\int _{x}^{\infty }{\frac {\mathrm {d} t}{t\left(t^{2}-1\right)\log t}}=\int _{x}^{\infty }{\frac {1}{t\log t}}\left(\sum _{m}t^{-2m}\right)\,\mathrm {d} t=\sum _{m}\int _{x}^{\infty }{\frac {t^{-2m}}{t\log t}}\,\mathrm {d} t\,\,{\overset {\left(u=t^{-2m}\right)}{=}}-\sum _{m}\operatorname {li} \left(x^{-2m}\right)$

Первый член li( x ) представляет собой обычную логарифмическую интегральную функцию ; выражение li( x ^р ) во втором члене следует рассматривать как Ei( ρ log x ) , где Ei — аналитическое продолжение экспоненциальной интегральной функции от отрицательных действительных чисел до комплексной плоскости с ветвью, разрезанной вдоль положительных действительных чисел.

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

$\pi _{0}(x)=\operatorname {R} (x)-\sum _{\rho }\operatorname {R} \left(x^{\rho }\right)-\sum _{m}\operatorname {R} \left(x^{-2m}\right)$

справедливо для x > 1 , где

$\operatorname {R} (x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\operatorname {li} \left(x^{1/n}\right)=1+\sum _{k=1}^{\infty }{\frac {\left(\log x\right)^{k}}{k!k\zeta (k+1)}}$

это R-функция Римана и µ ( n ) — функция Мёбиуса . Последняя серия для него известна как серия Грама . Поскольку log x < x для всех x > 0 , этот ряд сходится для всех положительных x по сравнению с рядом для e ^х . Логарифм в ряду Грама суммы по нетривиальному нулевому вкладу следует оценивать как ρ log x , а не log x. ^р .

Фолькмар Борнеманн доказал: если принять гипотезу о том, что все нули дзета-функции Римана простые, что

$\operatorname {R} \left(e^{-2\pi t}\right)={\frac {1}{\pi }}\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}t^{-2k-1}}{(2k+1)\zeta (2k+1)}}+{\frac {1}{2}}\sum _{\rho }{\frac {t^{-\rho }}{\rho \cos {\frac {\pi \rho }{2}}\zeta '(\rho )}}$

где ρ пробегает нетривиальные нули дзета-функции Римана и t > 0 .

Сумма по нетривиальным дзета-нулим в формуле для π ₀ ( x ) описывает колебания π ₀ ( x ) , в то время как остальные члены дают «гладкую» часть функции подсчета простых чисел, так что можно использовать

$\operatorname {R} (x)-\sum _{m=1}^{\infty }\operatorname {R} \left(x^{-2m}\right)$

как хорошая оценка π ( x ) для x > 1 . Фактически, поскольку второй член приближается к 0 при x → ∞ , а амплитуда «шумовой» части эвристически равна примерно √ x / log x оценка π ( x ) только по R( x ) столь же хороша, а колебания распределения простых чисел могут быть четко представлены с помощью функции

${\bigl (}\pi _{0}(x)-\operatorname {R} (x){\bigr )}{\frac {\log x}{\sqrt {x}}}.$

Неравенства

Вот несколько полезных неравенств для π ( x ) .

${\frac {x}{\log x}}<\pi (x)<1.25506{\frac {x}{\log x}}$

для х ≥ 17 .

Левое неравенство справедливо для x ≥ 17 , а правое неравенство справедливо для x > 1 . Константа 1,25506 равна log 113/113 30 до 5 десятичных знаков, как π ( x ) log x / x имеет максимальное значение при x = 113 .

Пьер Дюсар доказал в 2010 году:

${\frac {x}{\log x-1}}<\pi (x)\quad {\text{for }}x\geq 5393,$

и

$\pi (x)<{\frac {x}{\log x-1.1}}\quad {\text{for }}x\geq 60184.$

Вот некоторые неравенства для n- го простого pn _числа . Верхняя оценка принадлежит Россеру (1941): нижний - Дюсарту (1999):

$n(\log(n\log n)-1)<p_{n}<n{\log(n\log n)}\quad {\text{for }}n\geq 6.$

Левое неравенство справедливо для n ≥ 2 , а правое неравенство справедливо для n ≥ 6 .

Приближение n- го простого числа:

$p_{n}=n(\log(n\log n)-1)+{\frac {n(\log \log n-2)}{\log n}}+O\left({\frac {n(\log \log n)^{2}}{(\log n)^{2}}}\right).$

Рамануджан доказал, что неравенство

$\pi (x)^{2}<{\frac {ex}{\log x}}\pi \left({\frac {x}{e}}\right)$

справедливо для всех достаточно больших значений x .

В 2010 году Дюсарт доказал (предложение 6.6), что для n ≥ 688383

$p_{n}\leq n\left(\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}\right),$

и (предложение 6.7) что при n ≥ 3

$p_{n}\geq n\left(\log n+\log \log n-1+{\frac {\log \log n-2.1}{\log n}}\right).$

Совсем недавно Дюсарт доказал (теорема 5.1), что при x > 1

$\pi (x)\leq {\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2}{\log ^{2}x}}+{\frac {7.59}{\log ^{3}x}}\right),$

и что для x ≥ 88789

$\pi (x)>{\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2}{\log ^{2}x}}\right).$

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

Гипотеза Римана предполагает гораздо более жесткую границу ошибки оценки π ( x ) и, следовательно, более регулярное распределение простых чисел:

$\pi (x)=\operatorname {li} (x)+O({\sqrt {x}}\log {x}).$

Конкретно,

$|\pi (x)-\operatorname {li} (x)|<{\frac {\sqrt {x}}{8\pi }}\,\log {x},\quad {\text{for all }}x\geq 2657.$

Дудек (2015) доказал, что из гипотезы Римана следует, что для всех x ≥ 2 существует простое число p, удовлетворяющее условиям

$x-{\frac {4}{\pi }}{\sqrt {x}}\log x<p\leq x.$

См. также

• Постулат Бертрана
• Гипотеза Оппермана
• Рамануджан прайм

Внешние ссылки

• Крис Колдуэлл, The Nth Prime Page в The Prime Pages .
• Томас Оливейра и Силва, Таблицы функций подсчета простых чисел .
• Дудек, Адриан В. (2015), «О гипотезе Римана и разнице между простыми числами», Международный журнал теории чисел , 11 (3): 771–778, arXiv : 1402.6417 , Bibcode : 2014arXiv1402.6417D , doi : 10.1142/ С1793042115500426 , ISSN   1793-0421 , S2CID   119321107