THE FOLD / SPAWN / FIRST LIGHT / THE ADDITION CHAIN
THE ADDITION CHAIN
the shortest ladder of sums from 1 to n
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
An addition chain for a number n is the shortest ladder of additions that builds n starting from 1: a sequence 1 = a0, a1, …, ar = n where every term is the sum of two earlier ones. Its length r is the fewest multiplications needed to compute xn — each step multiplies two already-computed powers. The naive ‘multiply n times’ is terrible; the familiar binary (square-and-multiply) method is far better; but the truly shortest chain can beat even that. For n = 15 the binary method needs 6 multiplications, yet the chain 1, 2, 4, 5, 10, 15 needs only 5. Finding the shortest chain is a famously hard search — the heart of fast exponentiation in cryptography.
LIT verified live: an exhaustive shortest-chain search for n up to 40 returns chains that are valid (each term a sum of two earlier), compute xn exactly, and are never longer than the binary method — strictly shorter for n = 15, 23, 27, 39 — with the known anchors l(2k)=k, l(15)=5, l(23)=6, l(31)=7 all matching (window.__addchain). FIG no framing; the iterative-deepening search, the validity check, and the xn evaluation run in-browser.
LIT verified live: an exhaustive shortest-chain search for n up to 40 returns chains that are valid (each term a sum of two earlier), compute xn exactly, and are never longer than the binary method — strictly shorter for n = 15, 23, 27, 39 — with the known anchors l(2k)=k, l(15)=5, l(23)=6, l(31)=7 all matching (window.__addchain). FIG no framing; the iterative-deepening search, the validity check, and the xn evaluation run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at first-light — everything is built from 1: each new value is the sum of two that already exist, a ladder climbing from unity to n by the fewest possible steps. AVAN (AI) built the instrument: the iterative-deepening shortest-chain search, the chain-validity check, the xn evaluation, and the comparison against the binary method.
Credit as content: addition chains studied by Hansen, Knuth, Scholz, Brauer; the shortest-chain problem is A003313. The weave: David names first-light; I confirm the shortest ladder from 1 to n computes xn and can beat square-and-multiply.
Credit as content: addition chains studied by Hansen, Knuth, Scholz, Brauer; the shortest-chain problem is A003313. The weave: David names first-light; I confirm the shortest ladder from 1 to n computes xn and can beat square-and-multiply.
3 ONE DIMENSION
The shortest addition chain for n as a ladder from 1: each node is the sum of two earlier ones (arrows).
4 TWO DIMENSIONS · INTERACTIVE
Cycle n; the shortest chain, its length, the x^n check, and the comparison with the binary method are shown.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the shortest ladder of sums climbing from 1 to n.
AVAN’s addition (the inverse-companion): don’t multiply n times — reuse what you built. The inverse of ‘compute xn’ is ‘the shortest addition chain to n’: every power you already made can be squared or combined, so a handful of multiplications suffice. Magenta is the longer binary square-and-multiply path; green is the shortest chain. Reach n by reusing, not repeating.
LIT Genuine shortest addition chains (Scholz, Brauer, Knuth; sequence A003313). Verified live: an exhaustive iterative-deepening search for every n≤40 returns a valid addition chain (each term a sum of two earlier) that computes xⁿ exactly and is never longer than the binary square-and-multiply method — strictly shorter for n=15,23,27,39 — with anchors l(2^k)=k, l(15)=5, l(23)=6, l(31)=7 all matching (window.__addchain.chainsValid, .computesPow, .neverWorseThanBinary, .anchorsOk).
FIG No framing; the iterative-deepening search, the validity check, and the xⁿ evaluation run in-browser, and the returned length is provably minimal by construction. The AVAN inverse is honest — instead of multiplying n times, reuse what you built: the shortest addition chain to n squares or combines already-made powers so a handful of multiplications suffice. Magenta is the longer binary square-and-multiply path; green is the shortest chain. Reach n by reusing, not repeating.
FIG No framing; the iterative-deepening search, the validity check, and the xⁿ evaluation run in-browser, and the returned length is provably minimal by construction. The AVAN inverse is honest — instead of multiplying n times, reuse what you built: the shortest addition chain to n squares or combines already-made powers so a handful of multiplications suffice. Magenta is the longer binary square-and-multiply path; green is the shortest chain. Reach n by reusing, not repeating.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of FIRST LIGHT · David Lee Wise (ROOT0), with AVAN