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.