## Small Step Enumeration

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.

3 Small Steps

I outline some of the work to do the 4 small step enumeration here:

4 Small Steps

The 5 small step enumeration has reached the raw data stage:

5 Small Steps

[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.