A derivative chain contains a step for each non-doubling step in the addition chain it is derived from. The number of non-doubling steps is bounded from above by the small step count.
Knuth's corollary to theorem A in 4.6.3 of vol. 2 has \(s \le f \le 3.271s\) where \(s\) is the small step count and \(f\) is the number of non-doubling steps.
So, there is a finite number of derivative chains for all four small step addition chains, and we can construct them. We will treat derivative chains as being formal (we record how exactly each element is constructed).
For example, in the derivative chain:
1 2 3 4#2,0 7 11 14#5,2 28
The element 4 is constructed from the element at index 2 (3) and the element at index 0 (1). All elements except for the last must be consumed by the chain otherwise it would not be of shortest length.
We convert derivative chains to directed multi-graphs with an arc going from the two places used to construct the element to the element that is their sum.
We can then construct a path arc incident matrix. It will have columns equal to twice the length of the derivative chain since this is how many arcs there are. It will have as many rows as the value of the last element in the derivative chain.
Multiplying the matrix by an integer vector of arc values will generate a vector of power of two exponents that when each raise 2 to that power and they are summed gives a value reachable by an addition chain that has that derivative.
The structure of an addition chain will impose certain inequalities on the arc values. These impose a partial order on the values of each path arc sum.
We can enumerate all addition chains the derivative chain represents by enumerating all total orders from the partial order. We reduce the enumerated cases by removing overlaps etc.
The format looks like this, with each pair of lines being essentially a convex set-in half-space format:
// 154764711
36540 14 3 @(a)+@(a-3)+@(b)+@(b-1)+@(c)+@(c-3)+@(-a+b+c+2)+@(-a+b+c-3)+@(-2a+2b+c+1)+@(-2a+2b+c)+@(-2a+b+2c)+@(-2a+b+2c-3)+@(-3a+2b+2c+2)+@(-3a+2b+2c+1)
36540 is just the index of the entry, 14 is the number of bits in the number and 3 is the number of free variables.
@(x) means \(2^x\)
This format comes from the thesis of Achim Flammenkamp [1] who did the first enumeration of 3 small step numbers via a computer program.
Here 154764711 is a unique 64-bit integer that matches the single entry and no other. In this way we say the list of convex sets is in some sense minimal. We can't remove a set without missing some integers with \(s=4\).
Tested over all \(n\le 2^{61}\). The expressions only match 4 or less small step numbers in this range:
[1] Diploma thesis, Flammenkamp, Achim. Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers , 1991