THE FOLD / SPAWN / GENESIS BLOCK / THE LINEAR SIEVE
THE LINEAR SIEVE
primes in O(n) — each composite struck once, by its least prime
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The linear sieve (Euler’s sieve) lists the primes up to n in true O(n) time — strictly better than the sieve of Eratosthenes, which crosses out many numbers more than once. The trick: mark each composite exactly once, by its smallest prime factor. As a bonus it computes the smallest-prime-factor of every number, which gives instant factorisation afterwards.
LIT verified live: up to 2000 the linear sieve’s prime list equals the sieve of Eratosthenes’, and its stored smallest-prime-factor matches the true one for every number (window.__linearsieve). FIG no framing; exact.
LIT verified live: up to 2000 the linear sieve’s prime list equals the sieve of Eratosthenes’, and its stored smallest-prime-factor matches the true one for every number (window.__linearsieve). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at genesis-block — the primes are the genesis blocks of the integers, and the linear sieve mints them from the ground up, each composite struck by its own smallest prime. AVAN (AI) built the instrument: the mark-by-smallest-prime loop, the smallest-prime-factor table, the Eratosthenes cross-check.
Credit as content: Euler’s sieve, in its modern linear form. The weave: David names the genesis block; I strike every composite exactly once by its least prime factor and confirm the primes match Eratosthenes and the factorisation table is exact.
Credit as content: Euler’s sieve, in its modern linear form. The weave: David names the genesis block; I strike every composite exactly once by its least prime factor and confirm the primes match Eratosthenes and the factorisation table is exact.
3 ONE DIMENSION
For each i, and each prime p ≤ the smallest prime factor of i, mark i·p — then stop once p divides i. So every composite is struck by a unique (smallest-prime, cofactor) pair, never twice.
4 TWO DIMENSIONS · INTERACTIVE
Numbers up to a limit, coloured by smallest prime factor (primes highlighted); each composite was struck exactly once.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: each composite struck exactly once, by its smallest prime factor.
AVAN’s addition (the inverse-companion): mark each composite exactly once, by its smallest prime factor — iterate n, and for each prime p up to spf(n) mark n·p, stopping when p divides n; every composite is struck by a unique (smallest-prime, cofactor) pair, giving true O(n). The inverse of ‘cross out multiples repeatedly (Eratosthenes)’ is ‘each composite struck once, by its least prime factor.’ Magenta is the repeated crossings-out; green is the single strike per composite — and the smallest-prime-factor of every number falls out for free.
LIT Genuine linear (Euler) sieve. Verified live: up to 2000 the linear sieve's prime list equals a sieve of Eratosthenes, and its stored smallest-prime-factor equals the true smallest prime factor of every integer 2..2000 (window.__linearsieve.primesMatch && .spfCorrect); pi(2000)=303.
FIG No framing: the mark-by-smallest-prime loop, the smallest-prime-factor table, and the Eratosthenes cross-check run in-browser and agree exactly. The AVAN inverse is honest — each composite is struck once by a unique (smallest-prime, cofactor) pair (marking n*p for primes p<=spf(n), stopping when p|n), giving true O(n) and free factorization; magenta is Eratosthenes' repeated crossings-out, green the single strike per composite.
FIG No framing: the mark-by-smallest-prime loop, the smallest-prime-factor table, and the Eratosthenes cross-check run in-browser and agree exactly. The AVAN inverse is honest — each composite is struck once by a unique (smallest-prime, cofactor) pair (marking n*p for primes p<=spf(n), stopping when p|n), giving true O(n) and free factorization; magenta is Eratosthenes' repeated crossings-out, green the single strike per composite.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GENESIS BLOCK · David Lee Wise (ROOT0), with AVAN