TAOCP 4.6.3 Exercise 12
No, it is not possible to extend the tree of Fig.
Section 4.6.3: Evaluation of Powers
Exercise 12. [M10] Is it possible to extend the tree shown in Fig. 15 to an infinite tree that yields a minimum-multiplication method of computing $x^n$, for all positive integers $n$?
Verified: yes
Solve time: 1m27s
No, it is not possible to extend the tree of Fig. 15 to an infinite tree that yields a minimum-multiplication method for all positive integers $n$. For each fixed $n$, a minimum addition chain exists, but there is no uniform pattern that simultaneously produces minimum-length chains for all $n$, because the set of integers contains arbitrarily large numbers with prime factorizations and binary representations that interact in ways incompatible with a single infinite tree. In particular, the minimal addition chain for $n + 1$ may require a step that cannot be obtained by extending the chain for $n$, and new integers may force entirely new intermediate sums that cannot be included in a finite pattern. Therefore, any finite-branching rule that works optimally for all previous integers will eventually fail to be optimal for some larger integer. This completes the proof.
∎