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

функція, що дорівнює числу простих чисел, менших або рівних дійсному числу x

У математиці функція розподілу простих чисел, або пі-функція , — це функція, що дорівнює числу простих чисел, менших або рівних дійсному числу x[1][2]. Позначається (це ніяк не пов'язано з числом пі).

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

Історія

ред.

Великий інтерес у теорії чисел викликає швидкість зростання пі-функції[3][4]. Наприкінці XVIII століття Гаусс і Лежандр висунули припущення, що пі-функція оцінюється як

 

тобто, що

 

Це твердження — теорема про розподіл простих чисел. Воно еквівалентне твердженню

 

де   — інтегральний логарифм. Теорему про прості числа вперше довів 1896 року Жак Адамар і незалежно Валле-Пуссен, використовуючи дзета-функцію Рімана, яку 1859 року ввів Ріман.

Точніше зростання   зараз описують як

 

де   позначає O велике. Коли x не дуже велике,   перевищує  , проте різниця   змінює свій знак нескінченне число разів, найменше натуральне число, для якого відбувається зміна знака, називається числом Ск'юза.

Доведення теореми про прості числа, що не використовують дзета-функції або комплексного аналізу, знайшли 1948 року Атле Сельберг і Пал Ердеш (здебільшого незалежно)[5].

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

ред.

У таблиці показано зростання функцій   за степенями 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 %
102 25 3,3 5,1 4,000 25 %
103 168 23 10 5,952 16,8 %
104 1 229 143 17 8,137 12,3 %
105 9 592 906 38 10,425 9,59 %
106 78 498 6 116 130 12,740 7,85 %
107 664 579 44 158 339 15,047 6,65 %
108 5 761 455 332 774 754 17,357 5,76 %
109 50 847 534 2 592 592 1 701 19,667 5,08 %
1010 455 052 511 20 758 029 3 104 21,975 4,55 %
1011 4 118 054 813 169 923 159 11 588 24,283 4,12 %
1012 37 607 912 018 1 416 705 193 38 263 26,590 3,76 %
1013 346 065 536 839 11 992 858 452 108 971 28,896 3,46 %
1014 3 204 941 750 802 102 838 308 636 314 890 31,202 3,20 %
1015 29 844 570 422 669 891 604 962 452 1 052 619 33,507 2,98 %
1016 279 238 341 033 925 7 804 289 844 393 3 214 632 35,812 2,79 %
1017 2 623 557 157 654 233 68 883 734 693 281 7 956 589 38,116 2,62 %
1018 24 739 954 287 740 860 612 483 070 893 536 21 949 555 40,420 2,47 %
1019 234 057 667 276 344 607 5 481 624 169 369 960 99 877 775 42,725 2,34 %
1020 2 220 819 602 560 918 840 49 347 193 044 659 701 222 744 644 45,028 2,22 %
1021 21 127 269 486 018 731 928 446 579 871 578 168 707 597 394 254 47,332 2,11 %
1022 201 467 286 689 315 906 290 4 060 704 006 019 620 994 1 932 355 208 49,636 2,01 %
1023 1 925 320 391 606 803 968 923 37 083 513 766 578 631 309 7 250 186 216 51,939 1,92 %
1024 18 435 599 767 349 200 867 866 339 996 354 713 708 049 069 17 146 907 278 54,243 1,84 %
1025 176 846 309 399 143 769 411 680 3 128 516 637 843 038 351 228 55 160 980 939 56,546 1,77 %
1026 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 %
1027 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 перша колонка значень   — це послідовність A006880,   — послідовність A057835, а   — послідовність A057752.

Алгоритми обчислення пі-функції

ред.

Простий спосіб знайти  , якщо   не дуже велике, — скористатися решетом Ератосфена, яке видає прості, що не перевищують  , і підрахувати їх.

Більш продуманий спосіб обчислення   запропонував Лежандр: дано  , якщо   — різні прості числа, число цілих чисел, що не перевищують   і не діляться на всі   дорівнює

 

(де   позначає цілу частину). Отже, отримане число дорівнює

 

якщо   — це всі прості числа, що не перевищують  .

У 1870—1885 роках у серії статей Ернст Майссель[ru] описав (і використав) практичний комбінаторний спосіб обчислення  . Нехай   — перші   простих, позначимо   кількість натуральних чисел, що не перевищують  , які не діляться на жодне  . Тоді

 

Візьмемо натуральне  , якщо   і якщо  , то

 

Використовуючи цей підхід, Майссель вирахував   для  .

1959 року Деррік Генрі Лемер[en] розширив і спростив метод Майсселя. Визначимо, для дійсного   та для натуральних   величину   як кількість чисел, що не перевищують m і мають рівно k простих множників, причому всі вони перевищують  . Крім того, нехай  . Тоді

 

де сума явно завжди має скінченне число ненульових доданків. Нехай   — ціле, таке, що  , і нехай  . Тоді   і   при  . Отже

 

Обчислення   можна отримати так:

 

З іншого боку, обчислити   можна за допомогою таких правил:

  1.  
  2.  

Використовуючи цей метод і IBM 701, Лемер зумів обчислити  .

Надалі цей метод вдосконалили Lagarias, Miller, Odlyzko, Deleglise та Rivat[9].

Китайський математик Hwang Cheng використав такі тотожності:[10]

 
 

і, вважаючи  , виконуючи перетворення Лапласа обох частин і застосовуючи суму геометричної прогресії з  , отримав вираз:

 
 
 

Інші функції, що підраховують прості числа

ред.

Інші функції, що підраховують прості числа, також використовують, оскільки з ними зручніше працювати. Одна з них — функція Рімана, яку часто позначають як   або  . Вона має стрибок на 1/n для степенів простих  , причому в точці стрибка   її значення дорівнює півсумі значень по обидва боки від  . Ці додаткові деталі потрібні для того, щоб її можна було визначити зворотним перетворенням Мелліна. Формально визначимо   як

 

де p просте.

Також можна записати

 

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

 

Формула обернення Мебіуса дає

 

Використовуючи відоме співвідношення між логарифмом дзета-функції Рімана та функцією Мангольдта  , і використовуючи формулу Перрона отримаємо

 

Функція Рімана має твірну функцію

 

Функції Чебишова[en] — це функції, що підраховують степені простих чисел   з вагою  :

 
 

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

ред.

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

Існує такий вираз для   -функції Чебишова:

 

де

 

Тут   пробігає нулі дзета-функції в критичній смузі, де дійсна частина   лежить між нулем та одиницею. Формула істинна для всіх  . Ряд за коренями збігається умовно, і його можна взяти в порядку абсолютного значення зростання уявної частини коренів. Зауважимо, що аналогічна сума за тривіальними коренями дає останній доданок у формулі.

Для   маємо таку складну формулу

 

Знову ж, формула істинна для всіх  , де   — нетривіальні нулі дзета-функції, впорядковані за їхнім абсолютним значенням, і, знову, останній інтеграл береться зі знаком «мінус» і є такою самою сумою, але за тривіальними нулями. Вираз   у другому члені можна розглянути як  , де   — аналітичне продовження інтегральної показникової функції на комплексну площину з гілкою, вирізаною вздовж прямої  .

Отже, формула обернення Мебіуса дає нам[12]

 

істинне для  , де

 

називається R-функцією також на честь Рімана.[13] Останній ряд у ній відомий як ряд Грама[en][14] і збігається для всіх  .

Сума за нетривіальними нулями дзета-функції у формулі для   описує флуктуації  , тоді як інші доданки дають гладку частину пі-функції,[15] тому можна використати

 

як найкраще наближення для   для  .

Амплітуда «шумної» частини евристично оцінюється як   тому флуктуації в розподілі простих можна явно представити  -функцією:

 

Великі таблиці значень   доступні тут[7].

Нерівності

ред.

Тут виписано деякі нерівності для  .

 

Ліва нерівність виконується при  , а права — при  [16]

Нерівності для  -го простого числа  :

 

Ліва нерівність істинна при  , а права — при  .

Має місце така асимптотика для  -го простого числа  :

 

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

ред.

Гіпотеза Рімана еквівалентна точнішій межі помилки наближення   інтегральним логарифмом, а отже й регулярнішому розподілу простих чисел

 

Зокрема,[17]

 

Див. також

ред.

Примітки

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

Література

ред.

Посилання

ред.