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

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

тобто, що

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

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

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

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

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

Таблиці для пі-функції, x/ln x і li(x) У таблиці показано зростання функцій за степенями 10.

{| class="wikitable" style="text-align: right" ! 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 роках у серії статей описав (і використав) практичний комбінаторний спосіб обчислення . Нехай  — перші простих, позначимо кількість натуральних чисел, що не перевищують , які не діляться на жодне . Тоді

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

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

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

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

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

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

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

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

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

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

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

де p просте.

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

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

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

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

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

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

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

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

де

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Зокрема,

Див. також Теорема про розподіл простих чисел Постулат Бертрана Число Ск'юза Просте число Рамануджана

Примітки

Література

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

Посилання Chris Caldwell, The Nth Prime Page на сайті .