Addition chain search tree pruning by discarding non-minimal chains An addition chain is an ordered tuple of numbers, starting with $1$, such that each number after $1$ can be expressed as the sum of two smaller numbers in the chain.
An example of an addition chain is $1, 2, 4, 5, 9, 14, 23$.  This chain has minimal length of all addition chains ending with $23$.
Project Euler problem 122 requires computing the minimal lengths of addition chains ending with the numbers $1$ through $200$.  My algorithm iterated over chains of increasing length, discarding non-minimal chains and creating new chains by appending sums of pairs of elements of existing chains.  Although this algorithm got the right answer to the problem, I don't know if it is actually "safe" to discard non-minimal chains.  This inspired me to ask the following questions:
Say an addition chain $C$ is "prefix-minimal" if every prefix of $C$, including $C$ itself, is a minimal addition chain.


*

*Is every minimal chain prefix-minimal?

*For any $n$, does there exist a prefix-minimal chain ending with $n$?


Is every minimal chain prefix-minimal?
No.  Counterexample: $1, 2, 3, 5, 6, 11$ is minimal but not prefix-minimal.
For any $n$, does there exist a prefix-minimal chain ending with $n$?
No.  A Brauer chain is one in which each member $a_{k+1}$ can be expressed as $a_{k} + a_j$ for some $j$.  It can be seen that a prefix-minimal chain must be a Brauer chain.  It is known that not all numbers have a Brauer chain that is minimal length for that number; therefore, not all numbers have a prefix-minimal chain.
