It's possible to enumerate the infinite number of addition chains with a fixed number of small steps by enumerating a finite (yet often large) space of different objects (graphs for example).
The standard approach taken is to recognize that fixing the small step count at say \(s\) limits the non-doubling steps \(f\) in a chain such that \(s \le f \le 3.271s\). This is Knuth's [1] Corollary to Theorem A in §4.6.3.
We can therefor enumerate some alternate object that had the doubling steps removed. Mathematically enumeration results in a union of convex sets. The format we use to describe these convex sets comes from [2].
For example, the enumeration for \(s=0\) is:
// 1
1 1 1 @(a)
// 1 is a unique value that matches this convex set
@(a) is \(2^a\)
1 1 1 is and unique convex set number, the number of bits and the number of free variables in the convex set.
For \(s=1\):
// 3
1 2 2 @(a)+@(b)
We must have \(a > b \ge 0\) so we describe the bits from most significant to least.
Things may become clearer when we view \(s=2\):
// 7
1 3 3 @(a)+@(b)+@(c)
// 135
2 4 1 @(a)+@(a-5)+@(a-6)+@(a-7)
// 39
3 4 2 @(a)+@(a-3)+@(b)+@(b-1)
// 15
4 4 4 @(a)+@(b)+@(c)+@(d), a-b-c+d >= 0, -a+b+c-d >= -1
The comma separated list of conditions (\(a-b-c+d \ge 0, -a+b+c-d \ge -1\)) must be satisfied to match the convex set. Note that Knuth's [1] Theorem C in §4.6.3 gives 4 cases for 2 small steps generating 4 bit numbers. Two of those cases are combined above (Case 1 and 2 are convex set 4).
Flammenkamp [2] did the first computer enumeration of the \(s=3\) as an answer to question 15 in §4.6.3 in [1]. While writing a program for the \(s=4\) case I was postprocessing convex sets to detect and remove overlaps because the output is so huge. I was able to prune the \(s=3\) case from the original 200 cases to 150.
I outline some of the work to do the 4 small step enumeration here:
The 5 small step enumeration has a very large data set and can be found here:
[1] Knuth DE (1969), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA. , pp. 98-422.
[2] Flammenkamp A (1991), "Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers". Thesis at: Diplomarbeit an der Fakultät für Mathematik, Universität Bielefeld.