Как простые редеют: закон распределения

Простых бесконечно много, но с ростом чисел они встречаются всё реже — и реже по точному закону.

Функция $\pi(n)$ — количество простых чисел, не превосходящих $n$.

Мы знаем, что простые не кончаются. Но как именно они разбросаны? До 100 их 25, до 1000 — уже 168, до миллиона — 78 498. Доля простых падает. Можно ли описать это падение формулой? Гаусс ещё подростком, разглядывая таблицы простых, заметил закономерность, которую спустя век строго доказали Адамар и Валле-Пуссен.

Теорема о распределении простых

Главный результат звучит так:

$$\pi(n) \sim \frac{n}{\ln n}, \qquad n \to \infty,$$

где значок $\sim$ означает, что отношение левой и правой частей стремится к единице. Иначе говоря, простых до $n$ примерно $\dfrac{n}{\ln n}$ штук. Отсюда вытекает красивое следствие про «вероятность простоты»: случайно взятое число вблизи $n$ оказывается простым с вероятностью около $\dfrac{1}{\ln n}$. Чем больше $n$, тем реже простые — но убывает плотность медленно, как обратный логарифм.

Проверим на числах

Посчитаем точное $\pi(n)$ решетом и сравним с оценкой $n / \ln n$:

from math import log

def sieve_count(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
        p += 1
    return sum(is_prime)

for n in [100, 1000, 10000, 100000]:
    exact = sieve_count(n)
    approx = n / log(n)
    ratio = exact / approx
    print(f"n={n:>6}: pi={exact:>5}, n/ln_n={approx:8.1f}, otn={ratio:.3f}")

Вывод:

n=   100: pi=   25, n/ln_n=    21.7, otn=1.151
n=  1000: pi=  168, n/ln_n=   144.8, otn=1.161
n= 10000: pi= 1229, n/ln_n=  1085.7, otn=1.132
n=100000: pi= 9592, n/ln_n=  8685.9, otn=1.104

Как работает под капотом

Отношение в последнем столбце медленно ползёт к единице — это и есть смысл значка $\sim$. Сходимость нарочито неспешная: даже при $n = 100000$ ошибка около 10%. Более точное приближение даёт интегральный логарифм $\mathrm{li}(n) = \int_2^n \frac{dt}{\ln t}$, который «прилипает» к $\pi(n)$ гораздо плотнее. Но главное качественное наблюдение — плотность простых около $n$ ведёт себя как $1/\ln n$ — видно уже из простой формулы.

Частые ошибки

Первая ошибка — читать $\sim$ как «равно»: это лишь асимптотическое равенство отношений, абсолютная разность $\pi(n) - n/\ln n$ растёт. Вторая — путать натуральный логарифм $\ln$ (по основанию $e$) с десятичным $\lg$: в формуле строго $\ln$. Третья — думать, что раз простые редеют, они когда-нибудь иссякнут; редеют, но бесконечны.

Итог

• $\pi(n)$ — число простых до $n$.
• Теорема о распределении: $\pi(n) \sim n/\ln n$.
• Плотность простых около $n$ примерно $1/\ln n$ и убывает медленно.
• $\sim$ — про отношение, не про абсолютную разность.