# Properties of shortest addition chains for small numbers (e.g. up to 600)

Up to which values of $n$ do the following properties hold for strictly monotonically increasing, shortest addition chains (sac) $a=a_1,\dots,a_k$ (definitions below)?

a) There exists a sac for $n$ such that $a_k=n, a_i=n-a_{k-1}$ for some $i$ < $k$-1 and $a$ only contains values from a sac for $a_{k-1}$ with the same property and a sac for $a_i$ with the same property.

b) If $n\neq 3$, there exists a sac for $n$ with max 2 consecutive numbers (i.e. $\forall i \in \{1\dots k-2\}: a_{i+1} - a_i = 1 \Rightarrow a_{i+2}-a_{i+1} > 1$.

c) Both a) and b) together.

### Notes

a) implies that the sac is a star chain, so a) will not hold for $n$=12509 (the smallest value that does not have a star chain that is a sac).

b) implies that if $n\neq 3$, there is a sac for $n$ that starts with 1,2,4.

I checked the properties a), b) and c) programmatically up to $n=600$ for this programming competition, but not mathematically (and not with very clean code, either ;)

### Definitions

The following definitions are from Knuth's Art of Computer Programming, Volume 2, Seminumerical Algorithms.

An addition chain $a=a_1,\dots,a_k$ for $n$ is sequence of integers such that $a_1 = 1, a_k = n$ and $a_h = a_i + a_j$ for some $j\leq i$ < $h$ for all $h = 2,\dots,k$.

A strictly monotonically increasing, shortest addition chain (sac) for $n$ is an addition chain such that no shorter addition chain for $n$ exists and $a_{i+1} > a_i$ for all $i = 1,\dots,k-1$.

A star chain (aka Brauer chain) is an addition chain where $i=h-1$, i.e. $a_h = a_{h-1} + a_j$ for some $j\leq h-1$ for all $h = 2,\dots,k$.

-
I think your definition is missing something. Otherwise every $n$ has the single-element addition chain {$n$}. – TonyK Apr 13 '12 at 11:36
@TonyK: thanks, fixed it. – DaveBall aka user750378 Apr 13 '12 at 11:38
Have you seen the database at wwwold.iit.cnr.it/staff/giovanni.resta/ac which contains addition chains up to 1024? – Gerry Myerson Apr 14 '12 at 23:18
@Gerry, thanks for the link - I learned that Brauer is a synonym for star ;) The online resources I checked were oeis.org/A003313 and wwwhomes.uni-bielefeld.de/achim/addition_chain.html. – DaveBall aka user750378 Apr 15 '12 at 7:53

a) The property holds for all sacs. If $n = a_i + a_j$, any number that’s not in a sac of $a_i$ or $a_j$ is superfluous (not needed to create $n$). The hard thing is to choose sacs of $a_i$ and $a_j$ with the largest intersection.
b) True for $n<14759$ (by exhaustive search): every sac of 14759 starts with (1 2 3).
c) $\implies$ true for $n<14759$.