Math
Решето и плотность простых
Проведите решето руками на пронумерованных плитках: возьмите следующий делитель, предскажите, откуда начнётся его волна, и смотрите, как она вычёркивает кратные — уже вычеркнутые лишь задеваются. Рядом — pi(x) по счёту против приближений x/ln x и Li(x).
Что происходит
Решето Эратосфена на доске пронумерованных плиток. Возьмите следующий делитель — наименьшую ещё стоящую плитку — и скажите, откуда начнётся его волна: первое ещё стоящее кратное — всегда p², потому что каждое меньшее кратное k·p имеет меньший делитель k и уже вычеркнуто. Затем волна проходит по p², p² + p, …: стоящую плитку она вычёркивает, и та принимает цвет этого простого; уже вычеркнутую лишь задевает и считает, но не вычёркивает заново. Найденные простые собираются в строку под доской. Решето останавливается, когда квадрат следующего делителя выходит за доску — у любого составного до N есть делитель не больше √N, — и всё, что ещё стоит, — простые. На большой доске плитки становятся плотной картой, а лупа под курсором читает числа. График рядом считает pi(x) до своей границы против двух приближений, x/ln x и Li(x): грубое занижает на проценты, Li почти лежит на счёте, а 60180 — последнее N до двух миллионов, где x/ln x ошибается больше чем на десять процентов.
Уравнения модуля
Уравнения решето считает pi(N) точно - это определение, а не оценка pi(10^3) = 168, pi(10^4) = 1229, pi(10^5) = 9592, pi(10^6) = 78498 N / ln N ЗАНИЖАЕТ: при 10^3 на 13.83 %, при 10^4 на 11.66 %, при 10^5 на 9.45 %, при 10^6 на 7.79 % Li(N) = интеграл от 2 до N от dt/ln t ошибается на доли процента: 5.098 %, 1.309 %, 0.383 %, 0.164 % на тех же десятичных порядках Li(10^4) = 1245.092052, Li(10^6) = 78626.503996 задача: 60180 - ПОСЛЕДНЕЕ N до двух миллионов, где N/ln N отклоняется более чем на десять процентов (10.0004 %); при 60181 отклонение 9.9990 % - найдено ОДНИМ ПРОХОДОМ по префиксным счётам, потому что ошибка НЕ монотонна: она пересекает линию десяти процентов 159 раз, а бисекция, стоявшая здесь раньше, давала ответ 60180 стоимость решета, две РАЗНЫЕ величины: первых вычёркиваний = N − pi(N) − 1 ТОЧНО (8770 при 10^4, 921501 при 10^6) - каждое составное число вычёркивается впервые ровно один раз всего обращений ~ сумма N/p по p <= sqrt(N) (16981 против 18028 при 10^4, отношение 0.9419; 0.9654 при 10^6) - решето начинается с p² и никогда не трогает меньшие кратные наибольший промежуток между простыми: 8 после 89, 20 после 887, 36 после 9551, 72 после 31397 - все пока ниже ln²N
