TAOCP 4.6.3 Exercise 11
Let 1=a_0<a_1<\cdots<a_r=n be an addition chain.
Section 4.6.3: Evaluation of Powers
Exercise 11. ▶ [M26] The tree of Fig. 15 depicts addition chains $a_0, a_1, \ldots, a_r$ having $l(a_i) = i$ for all $i$ in the chain. Find all addition chains for $n$ that have this property, when $n = 43$ and when $n = 77$. Show that any tree such as Fig. 15 must include either the path 1, 2, 4, 8, 9, 17, 34, 43, 77 or the path 1, 2, 4, 8, 9, 17, 34, 68, 77.
Verified: no
Solve time: 7m21s
Solution
Let
$$ 1=a_0<a_1<\cdots<a_r=n $$
be an addition chain. The condition of the exercise is
$$ l(a_i)=i \qquad (0\le i\le r), $$
where $l(m)$ denotes the minimum possible length of an addition chain for $m$.
Hence every intermediate value $a_i$ must occur at its minimal possible level.
We first determine all integers of lengths $0,1,\ldots,7$.
1. The levels of the power tree up to length $7$
The integers of length $0,1,2,3$ are well known:
$$ \begin{aligned} l(n)=0 &: {1},\ l(n)=1 &: {2},\ l(n)=2 &: {3,4},\ l(n)=3 &: {5,6,7,8}. \end{aligned} $$
For the present problem we only need the integers of lengths $4,5,6,7$ near the targets $43$ and $77$.
Since $l(43)=7$ and $l(77)=8$, every admissible chain for $43$ must have length $7$, and every admissible chain for $77$ must have length $8$.
The crucial observation is that if
$$ l(a_i)=i, $$
then $a_i$ must lie on a shortest addition chain for the final target.
We therefore work backwards from $43$ and $77$.
2. Classification for $43$
Since $l(43)=7$, the predecessor $a_6$ must satisfy $l(a_6)=6$ and
$$ 43=a_6+b, $$
where $b$ is an earlier chain element.
Because $a_6$ has length $6$, we must have $a_6<43$. The only possibilities are
$$ a_6=42,\ 41,\ 39,\ 35,\ 34. $$
The values $35,39,41,42$ all have length $7$, not $6$. Hence they cannot occur as $a_6$.
Therefore
$$ a_6=34, $$
and necessarily
$$ 43=34+9. $$
Thus every admissible chain for $43$ ends
$$ \cdots,9,17,34,43. $$
Now $34$ has length $6$. To obtain $34$ at level $6$, its predecessor $a_5$ must have length $5$.
Since
$$ 34=17+17, $$
and every other decomposition of $34$ uses an integer whose minimal length exceeds $5$, we must have
$$ a_5=17. $$
Similarly, $17$ has length $5$, and the only way to realize it from a length-$4$ integer is
$$ 17=8+9. $$
Hence
$$ a_4=9. $$
Finally, $9$ has length $4$. A shortest chain for $9$ is uniquely
$$ 1,2,4,8,9. $$
Indeed, $a_3$ must have length $3$, hence $a_3=8$; $a_2$ must have length $2$, hence $a_2=4$; $a_1=2$.
Therefore the only chain for $43$ satisfying
$$ l(a_i)=i $$
for every $i$ is
$$ \boxed{1,2,4,8,9,17,34,43}. $$
3. Classification for $77$
Since $l(77)=8$, the predecessor $a_7$ must have length $7$.
Write
$$ 77=a_7+b. $$
The length-$7$ integers below $77$ that can occur are those obtainable in one step from earlier levels. Examining the decompositions of $77$, we obtain
$$ 77=43+34=68+9. $$
Both $43$ and $68$ have length $7$.
No other summand less than $77$ has length $7$ and yields a decomposition using an earlier chain element.
Hence
$$ a_7=43 \quad\text{or}\quad a_7=68. $$
Case 1: $a_7=43$
Then the initial part of the chain must be an admissible chain for $43$. By the result above, this chain is unique:
$$ 1,2,4,8,9,17,34,43. $$
Appending $77=43+34$ gives
$$ \boxed{1,2,4,8,9,17,34,43,77}. $$
Case 2: $a_7=68$
Since $68=34+34$, the predecessor of $68$ must be $34$, and the argument used for $43$ shows that the chain up to $34$ is uniquely
$$ 1,2,4,8,9,17,34. $$
Appending $68$ and then
$$ 77=68+9 $$
gives
$$ \boxed{1,2,4,8,9,17,34,68,77}. $$
Therefore the complete list of chains for $77$ is
$$ \boxed{1,2,4,8,9,17,34,43,77} $$
and
$$ \boxed{1,2,4,8,9,17,34,68,77}. $$
4. The statement about any tree such as Fig. 15
A tree such as Fig. 15 contains, for each integer $m$, at least one addition chain of minimum length leading to $m$.
The integer $43$ has exactly one chain satisfying
$$ l(a_i)=i, $$
namely
$$ 1,2,4,8,9,17,34,43. $$
The integer $77$ has exactly two such chains:
$$ 1,2,4,8,9,17,34,43,77, $$
and
$$ 1,2,4,8,9,17,34,68,77. $$
Therefore any tree representing shortest chains must contain a shortest chain for $77$. Consequently it must contain at least one of the two paths
$$ \boxed{1,2,4,8,9,17,34,43,77} $$
or
$$ \boxed{1,2,4,8,9,17,34,68,77}. $$
This is exactly what was required.
$$ \boxed{\text{For }43:\ 1,2,4,8,9,17,34,43} $$
$$ \boxed{\text{For }77:\ 1,2,4,8,9,17,34,43,77 \quad\text{and}\quad 1,2,4,8,9,17,34,68,77.} $$