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

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