| 27,6310 | 26,5901 | 3,9146 |
| 1 000 000 000 000 000 | 34,5388 | 33,5069 | 3,0794 |
| 1 000 000 000 000 000 000 | 41,4465 | 40,4204 | 2,5386 |
Таблица 3.3.
Представляется разумным следующее утверждение: N/?(N) близко к ln N, причем тем ближе, чем больше становится N.
У математиков есть специальная запись для этого: N/?(N) ~ ln N. (Читается так: «N, деленное на ?(N), асимптотически стремится к ln N»). Волнистый знак в этой формуле по науке называется «тильда», однако, судя по моему опыту, математики нередко называют его просто «волной».
Если слегка переоформить этот факт, следуя обычным правилам алгебры, то мы получим следующее утверждение.
Теорема о распределении простых чисел ?(N) ~ N/ln N
Разумеется, мы эту теорему не доказали — мы просто увидели, что такое утверждение правдоподобно. Это очень важный результат, настолько важный, что он называется Теоремой о распределении простых чисел. Это не какая-то там теорема о распределении простых чисел, нет, а Теорема о Распределении Простых Чисел. Специалисты по теории чисел нередко пишут просто «ТРПЧ», и в этой книге мы так и будем поступать.
IX. И наконец, получим два следствия из ТРПЧ (в предположении, конечно, что она верна). Чтобы вывести эти следствия, сначала заметим, что в некотором смысле (логарифмическом смысле!) при работе со всеми числами вплоть до некоторого большого N большинство из этих чисел вполне сравнимы по величине с самим N. Например, среди всех чисел от 1 до одного триллиона более 90 процентов имеют 12 или более разрядов и в этом смысле вполне сравнимы с триллионом (у которого 13 разрядов), а не, скажем, с одной тысячей (с ее четырьмя разрядами).
Если на интервале от 1 до N имеется N/ln N простых чисел, то средняя плотность простых в этом интервале составляет 1/ln N. А поскольку большинство чисел в этом интервале сравнимы по размеру с числом N в том грубом смысле, который я только что описал, то справедливым будет заключение, что в районе числа N плотность простых чисел есть 1/ln N. Именно так и есть. В конце первого раздела данной главы мы подсчитали число простых в каждом блоке из 100 чисел, предшествующих 100, 500, 1000, 1 миллиону и 1 триллиону. Результаты этих подсчетов были такими: 25, 17, 14, 8 и 4. Соответствующие значения выражения 100/ln N (т.е. его значения при N = 100, 500 и т.д). с точностью до ближайшего целого числа таковы: 22, 16, 14, 7 и 4. Другой способ выразить то же самое — это сказать, что в окрестности большого числа N вероятность того, что некоторое число окажется простым, ~ 1/ln N.
Руководствуясь той же грубой логикой, можно оценить величину N-го простого числа. Рассмотрим отрезок числового ряда от 1 до K для какого-нибудь большого числа K. Если в этом интервале простых чисел, то в среднем следует ожидать, что первым простым, которое мы встретим, будет число К:C, вторым — число 2K:C, третьим — 3K:C и т.д. N- е простое будет находиться где-то около числа NK:C, а C- е (другими словами, последнее простое в этом интервале) окажется около числа K:C, что, понятно, равно просто K. И вот, если верна ТРПЧ, то количество простых чисел C есть К/ln K, а потому N-е простое в действительности встретится вблизи числа NK:(К/ln K), или, другими словами, вблизи числа Nln K. Поскольку большинство чисел в этом интервале сравнимы по величине с числом K, здесь можно поменять местами N и K, а потому N-е простое есть по величине ~ N/ln N. Я знаю, что такое рассуждение выглядит небольшим жульничеством, но в действительности оно дает неплохую оценку, которая к тому же становится все лучше и лучше «по принципу волны». Эта оценка предсказывает, например, что триллионное простое число равно 27 631 021 115 929, а на самом деле триллионное простое число есть 30 019 171 804 121, так что ошибка составляет 8 процентов. Выраженные в процентах ошибки для тысячного, миллионного и миллиардного простого числа равны соответственно 13, 10 и 9.
Следствия из ТРПЧ Вероятность того, что число N простое, ~ 1/ln N.
N-е простое число ~ Nln N.
Эти утверждения не просто следуют из ТРПЧ; сама ТРПЧ также следует из них. Если математически доказать справедливость любого из них, то в качестве следствия получится ТРПЧ. Каждый из этих результатов равносилен ТРПЧ, и его можно считать просто альтернативной формулировкой этой теоремы. В главе 7.viii мы познакомимся с другим, более важным способом переформулировать ТРПЧ.
