Is There a Best Way to Compute $x^n$? — The Theory of Addition Chains

To compute $x^{10}$ from $x^1$, our gizmo multiplies any two powers we have already computed: $x^a \times x^b = x^{a+b}$. Notice that $x$ itself doesn’t matter—only the sequence of exponents matters! Starting from $1$ (which we have for free), each step produces a new number that is the sum of two earlier numbers in the sequence. This sequence is called an addition chain, and its length (excluding the initial $1$) is the number of multiplications.

For $n = 10$, the shortest possible length is $l(10) = 4$, achievable via two illuminatingly different philosophies: Path A ($1, 2, 4, 8, 10$) greedily doubles three times ($1 \to 2 \to 4 \to 8$) and then adds the saved $2$. Path B ($1, 2, 4, 5, 10$) makes a “strategic sacrifice” after $4$, adding $4 + 1 = 5$ so that a single final doubling ($5 + 5 = 10$) lands straight on $10$!

Because doubling is the fastest way to grow a number, there is a slick rule for turning the binary representation of $n$ into an addition chain: Write $n$ in base 2, remove the leftmost $\mathtt{1}$, replace each $\mathtt{0}$ with $\mathbf{D}$ (“double”) and each $\mathtt{1}$ with $\mathbf{D1}$ (“double, then add 1”).

For $n = 21 = 10101_2$, stripping the leading $\mathtt{1}$ leaves $\mathtt{0101} \to \mathbf{D, D1, D, D1}$, producing $1, 2, 4, 5, 10, 20, 21$ (6 steps, which is optimal!). Some authors claimed the Binary Method always yields the shortest chain—but as Knuth notes, that fails already at $n = 15 = 1111_2$, where the Binary Method takes 6 steps ($1, 2, 3, 6, 7, 14, 15$), whereas factoring $15 = 3 \times 5$ via $1, 2, 3, 6, 12, 15$ takes only 5 steps!

Addition chains harbor breathtaking surprises that refute seemingly obvious conjectures:

Surprise 1 — Doubling $n$ Doesn’t Always Cost an Extra Step ($l(2n) = l(n)$): Since doubling is the most efficient step in an addition chain, it feels certain that the shortest chain for $2n$ must be the shortest chain for $n$ followed by one doubling: $l(2n) = l(n) + 1$. False! For $n = 191$, the shortest chain requires $l(191) = 11$ steps. Yet for $2 \times 191 = 382$, we also have $l(382) = 11$ steps! By using a Fibonacci-like leap ($4, 5, 9, 14, 23$) and reusing $14$ at the end, $382$ lands in the exact same number of steps as $191$.

Surprise 2 — Hansen’s 1958 Star-Chain Refutation ($l(n) < l^*(n)$): A star chain requires every step to use the immediately preceding number ($a_k = a_{k-1} + a_m$). In 1958, Walter Hansen proved that not every minimal chain is a star chain, starting with the monstrous counterexample $n = 2^{6106} + 2^{3048} + 2^{2032} + 2^{1016} + 1$.

Experience the delight of crafting an addition chain yourself! Pick a target puzzle below, then click any two glowing number tiles in your current chain to add them together (or click the same tile twice to double it). Our friendly mathematical coach will cheer you on and show your live dependency arcs right below.

In accordance with the HCJ-SED engineering specification, “Agentic AI” refers not to the mathematical addition chains themselves, but to the autonomous roster of six specialized AI Critique & Engineering Agents tasked with vetting the mathematics, enforcing spatial locality, designing tactile candy affordances, eliminating console warnings, and ensuring zero user friction.

Below is the transparent v1.0 $\to$ v2.0 Stringent Audit Scorecard showing how each LLM-designated build agent was graded against a strict 100-point rubric, along with a live interactive DOM & Mathematical Self-Audit Runner.