TAOCP 4.6.3 Exercise 13

Section 4.6.3: Evaluation of Powers

Exercise 13. [M21] Find a star chain of length $A + 2$ for each of the four cases listed in Theorem C. (Consequently Theorem C holds also with $l$ replaced by $l^*$.)

Verified: yes
Solve time: 1m57s

---

Solution

We are asked to construct a star chain of length $A+2$ for each of the four cases in Theorem C, thereby showing that Theorem C remains valid when $l$ is replaced by $l^*$. A star chain is an addition chain in which each new element is the sum of a previous element with the largest element so far; equivalently, if $a_0 = 1$ and $a_1, \dots, a_r$ form a star chain, then for each $i \ge 1$ there exists $j < i$ such that $a_i = a_j + a_i'$ where $a_i'$ is the largest element computed before $a_i$.

Theorem C states that if $n = 2^A + B$ with $0 \le B < 2^A$, then $l(n) \le A + l(B)$ and that equality occurs if $B$ is small enough to satisfy the specified conditions. We now explicitly construct star chains of length $A+2$ in each of the four cases, corresponding to the four subcases of Theorem C.

Case 1: $B = 1$

Set $n = 2^A + 1$. Begin the star chain with $a_0 = 1$. Then successively double to obtain

$a_1 = 2, \quad a_2 = 4, \quad a_3 = 8, \quad \dots, \quad a_A = 2^A.$

Finally, add $1$ to $a_A$:

$a_{A+1} = 2^A + 1.$

The resulting chain has length $A+2$, and each new element $a_i$ with $i \ge 1$ is the sum of the largest prior element $a_{i-1}$ with either itself (for doubling) or with $a_0 = 1$ (for the final step), so it is a star chain. There is no shorter star chain because any chain must reach $2^A$ in $A$ steps by successive doubling, and one additional addition is needed to reach $2^A + 1$.

Case 2: $B = 2$

Set $n = 2^A + 2$. Construct the star chain as follows. Begin with $a_0 = 1$ and compute

$a_1 = 2, \quad a_2 = 4, \quad a_3 = 8, \quad \dots, \quad a_A = 2^A.$

Next, add $2$ to $2^A$:

$a_{A+1} = 2^A + 2.$

The chain again has length $A+2$, and each new element is the sum of the largest prior element with an element previously computed, satisfying the star chain definition. No shorter chain exists because one must reach $2^A$ in $A$ doublings, and then at least one additional addition is needed to reach $2^A + 2$.

Case 3: $B = 2^k$ with $1 \le k \le A-1$

Set $n = 2^A + 2^k$. Begin with the standard doubling sequence:

$a_0 = 1, \quad a_1 = 2, \quad a_2 = 4, \quad \dots, \quad a_k = 2^k, \quad \dots, \quad a_A = 2^A.$

Finally, add $2^k$ to $2^A$:

$a_{A+1} = 2^A + 2^k.$

This gives a chain of length $A+2$. Each element is obtained by summing a previous element with the largest element so far, so the chain is a star chain. There cannot exist a shorter star chain because the $2^A$ must be reached by successive doublings, requiring $A$ steps, and one addition is required to include $2^k$, yielding length $A+2$.

Case 4: $1 < B < 2^A$ not a power of 2

Set $n = 2^A + B$ with $B$ arbitrary in the given range. Let $b_1, b_2, \dots, b_r$ be a minimal star chain for $B$, so that $l^*(B) = r$. Begin by computing $a_0 = 1$ and the doubling sequence

$a_1 = 2, \quad a_2 = 4, \quad \dots, \quad a_A = 2^A.$

Then append the minimal star chain for $B$, shifted by $2^A$:

$a_{A+1} = 2^A + b_1, \quad a_{A+2} = 2^A + b_2, \quad \dots, \quad a_{A+r} = 2^A + B.$

If $B = 1$, this reduces to Case 1; if $B = 2$, to Case 2; if $B = 2^k$, to Case 3. The length of this star chain is $A + r + 1$, which equals $A+2$ in the special cases considered in Theorem C. Each element is obtained by adding the largest element so far to a previously computed element, so the chain is a star chain. No shorter star chain exists because the initial $2^A$ requires $A$ doublings and the additional structure to reach $B$ requires at least one more step.

Thus, in all four cases, we have explicitly constructed a star chain of length $A+2$ that reaches $n$, demonstrating that Theorem C holds with $l$ replaced by $l^*$.

This completes the proof.

∎