Math
The sieve and the density of primes
Work the sieve by hand on numbered tiles: take the next divisor, predict where its wave starts, and watch it strike its multiples - the ones already struck are only touched. Beside it, pi(x) counted against the approximations x/ln x and Li(x).
What happens
Eratosthenes' sieve on a board of numbered tiles. Take the next divisor - the smallest tile still standing - and say where its wave will start: the first multiple still standing is always p², because every smaller multiple k·p has the smaller factor k and is already out. The wave then passes over p², p² + p, …: a tile it finds standing is struck and takes that prime's colour; a tile already struck is only touched and counted, never struck again. Found primes gather in a row under the board. The sieve stops when the next divisor squared is past the board - every composite up to N has a factor at most √N - and what still stands are the primes. On a large board the tiles become a dense map; a magnifier under the cursor reads the numbers. The chart beside it counts pi(x) up to its own limit against two approximations, x/ln x and Li(x): the rough one undershoots by percents, Li lies almost on the count, and 60180 is the last N below two million where x/ln x is off by more than ten percent.
Equations used in the module
Equations the sieve counts pi(N) exactly - that is the definition, not an estimate pi(10^3) = 168, pi(10^4) = 1229, pi(10^5) = 9592, pi(10^6) = 78498 N / ln N UNDERSHOOTS: at 10^3 by 13.83 %, at 10^4 by 11.66 %, at 10^5 by 9.45 %, at 10^6 by 7.79 % Li(N) = integral from 2 to N of dt/ln t misses by a fraction of a percent: 5.098 %, 1.309 %, 0.383 %, 0.164 % on the same decades Li(10^4) = 1245.092052, Li(10^6) = 78626.503996 the task: 60180 is the LAST N up to two million where N/ln N is off by more than ten percent (10.0004 %); at 60181 it is 9.9990 % - found by ONE PASS over the prefix counts, because the error is NOT monotone: it crosses the ten-percent line 159 times, and the bisection that used to stand here answered 60180 cost of the sieve, two DIFFERENT quantities: first crossings = N − pi(N) − 1 EXACTLY (8770 at 10^4, 921501 at 10^6) - each composite is struck for the first time exactly once total touches ~ sum of N/p over p <= sqrt(N) (16981 against 18028 at 10^4, ratio 0.9419; 0.9654 at 10^6) - the sieve starts at p² and never touches the smaller multiples largest prime gap: 8 after 89, 20 after 887, 36 after 9551, 72 after 31397 - all still below ln²N
