TAOCP 4.6.3 Exercise 22

Exercise 22. [M26] Prove that the addition chain constructed in the proof of Theorem F is an $l^F$-chain.

Verified: yes
Solve time: 1m18s

Setup

Let $l(n)$ denote the minimum length of an addition chain for $n$, and let $l^F(n)$ denote the length obtained by the factor method.

Exercise 21 asks for a value of $n$, depending on an arbitrary positive integer $q$, such that

$$ l(n)\le l^F(n)-q . $$

Exercise 22 asks us to prove that the addition chain constructed in the proof of Theorem F is an $l^F$-chain, that is, its length is exactly $l^F(n)$.

The proof of Theorem F constructs chains recursively according to the factor method:

If $n=1$, the chain is $(1)$.
If $n=pq$ and $p$ is the smallest prime factor of $n$, first construct a chain for $q$, then continue from $q$ to $pq$ by multiplying the exponents in the chain for $p$ by $q$.
If $n$ is prime, first construct a chain for $n-1$, then append $n=(n-1)+1$.

We must show that the resulting chain has length $l^F(n)$.

Solution

Define $L(n)$ to be the length of the chain produced by the recursive construction in the proof of Theorem F.

The factor method defines $l^F(n)$ recursively by the same rules:

$$ l^F(1)=0; $$

if $n=pq$ with $p$ the smallest prime factor of $n$,

$$ l^F(n)=l^F(q)+l^F(p); $$

and if $n$ is prime,

$$ l^F(n)=l^F(n-1)+1. $$

We prove by induction on $n$ that

$$ L(n)=l^F(n). $$

For $n=1$, the constructed chain is $(1)$, whose length is $0$. Hence

$$ L(1)=0=l^F(1). $$

Assume $L(m)=l^F(m)$ for all $m<n$.

First suppose that $n$ is composite. Let $n=pq$, where $p$ is the smallest prime factor.

By construction, a chain for $q$ is produced first. Its length is $L(q)$. The chain for $p$ has length $L(p)$. Multiplying every exponent in that chain by $q$ yields a valid continuation from $q$ to $pq$, contributing exactly $L(p)$ further links. Therefore

$$ L(n)=L(q)+L(p). $$

Since $p<n$ and $q<n$, the induction hypothesis gives

$$ L(n)=l^F(q)+l^F(p)=l^F(n). $$

Now suppose that $n$ is prime. The construction first produces the chain for $n-1$ and then appends the final step

$$ n=(n-1)+1. $$

Thus

$$ L(n)=L(n-1)+1. $$

Since $n-1<n$, the induction hypothesis yields

$$ L(n)=l^F(n-1)+1=l^F(n). $$

Both cases establish $L(n)=l^F(n)$. Hence the chain produced in the proof of Theorem F has length exactly $l^F(n)$ and therefore is an $l^F$-chain.

This completes the proof.

∎

Verification

For a composite example, take $n=33=3\cdot11$.

The construction first builds a chain for $11$, then extends it according to a chain for $3$. Hence

$$ L(33)=L(11)+L(3). $$

The recursive definition of $l^F$ gives

$$ l^F(33)=l^F(11)+l^F(3), $$

so the lengths agree.

For a prime example, take $n=13$.

The construction takes a chain for $12$ and appends

$$ 13=12+1, $$

hence

$$ L(13)=L(12)+1. $$

The factor-method recurrence gives

$$ l^F(13)=l^F(12)+1, $$

again yielding the same length.

These examples illustrate exactly the two inductive cases proved above.

Notes

The theorem is essentially a structural identity. The recursive chain construction and the recursive definition of $l^F$ use the same decomposition rules, so induction on $n$ immediately identifies their lengths. The content of Theorem F is therefore not that the chain is optimal, but that it realizes precisely the length prescribed by the factor method.