An addition chain for an integer $n$ is any finite list of integers where the first entry is 1 and the last entry is $n$, and where every entry is the sum of two (possibly non-consecutive) entries that occur earlier in the list.
I was reading this, and found the shortest addition chain for many numbers. However, I was wondering if there was a more elegant, non exhaustive search method, to find the shortest addition chain for the number $100$? If I were asked to find the shortest addition chain for $100$, is there a way I could manually do this without listing out every possibility?
From what I've read, we don't know a fast way to find the shortest addition chain for a given $n$. In brief, the problem is that it's hard to tell whether you're making progress: if you have part of an addition list, can you tell whether it's close to being the shortest possible addition list for $n$?
If we could tell whether a partial list is close to being the shortest list for $n$, it would help guide the normally-exhaustive search and make it more efficient. For example, you might hope that you could find the shortest addition list for $n$ by guessing two factors $a+b=n$, finding the shortest lists for $a$ and $b$, then joining those lists together. That would streamline search (it's an instance of the optimal substructure property; some efficiently-solvable problems have this property). But unfortunately addition lists don't work that way, and in general we haven't found any way to measure whether our partial solution is close to being the optimal one.
Instead, what we currently have are relatively fast approximate algorithms to find solutions that might be close to the shortest length.