An addition chain for $n$ is a sequence of integers $1=a_0<a_1<...<a_r=n$ with $a_i=a_j+a_k,i>j\ge k\ge 0$. We say $r$ is the addition chain length. We define the length of the smallest addition chain for $n$ by $l(n)$.

We have a measure of complexity of addition chains called the small step count. We define $s(n)=l(n)-\lambda(n)$ where $\lambda(n)=\lfloor {log_2(n)}\rfloor$.

If $s(n)=0$ we have $n=2^a$. With $s(n)=1$ we have $n=2^a+2^b,a>b\ge0$. These two cases can be seen with simple limits on $n$ and was first done in 1894 [1]. With $s(n)=2$ things get more complicated. We have 4 cases:

$n=2^a+2^b+2^c,a>b>c\ge0$

$n=2^a+2^b+2^c+2^d,a>b>c>d,1\ge a-b-c+d >= 0$

$n=2^a+2^{a-5}+2^{a-6}+2^{a-7},a\ge7$

$n=2^a+2^{a-3}+2^b+2^{b-1},a>b+3,b\ge1$

Knuth [2] in 1969 has laborious proofs of these cases (stated as 5 cases) in section 4.6.3. He asked though in question 15 to write a computer program to enumerate the $s(n)=3$ case.

Flammenkamp [3] in 1991 wrote the computer program and found 200 cases.

It's clear from the way these cases are constructed that each case has the power of 2 exponents as lattice points in a convex set in $R^{v(n)}$. Here $v(n)$ is the hamming weight of $n$. These are expressed in half-space format. It's clear that some cases could be removed if they are subsets of the unions of other cases. If the union of multiple cases is itself a convex set, we could replace multiple cases with their union. This process can be repeated until each convex set has a unique single vector of exponents as it's member that prevents further reduction. This reduced the $s(n)=3$ from 200 to 150 cases.

This explodes with $s(n)=4$. A new computer program I wrote can enumerate all the cases in under two minutes. It generates 251213 cases. Reducing the number of convex sets by detecting the subsets as mentioned above yielded 40206 cases. This process though is expensive. I detect if two convex sets ($U_1$,$U_2$) have a non-empty intersection. If they do then I compute $U_1\smallsetminus U_2$ as a union of convex sets. This process is repeated in the hopes that the union of convex sets becomes empty and $U_1$ can be discarded.

The case $s(n)=5$ took about 2 weeks to run and has generated 240439903 cases. It's clear I need some different approach to removing these overlaps. No algorithm that's $O(n^2)$ or worse I think has any hope of working. So, the question is are there tricks I can use here to help me reduce the number of cases?

Why do we care? Well, it seems remarkable that $v(n)$ appears to be bounded from above with $s(n)+1\le v(n)\le 2^{s(n)}$ The enumeration clearly shows this for $s(n)\le 5$. To get confidence in the enumeration I check it by making sure the convex sets contain the exponents for all known $n$ with $s(n)\le5$ with $n\le 2^{63}$ (the limits of direct calculations and storage). I can only do this I think if the number of convex sets is much smaller. I expect a vector equivalent of the Frobenius Number might say that if you can test all cases up until some particular vector you have essentially exhausted all cases.

1: Goulard, A. Question 393, L'Intermédiaire des Mathématiciens, Vol. 1, 1894

2: Knuth, Donald E. The art of computer programming, 2: seminumerical algorithms, 1969

3: Flammenkamp, A. Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers 1991