Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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 ;)


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

share|cite|improve this question
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 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 and – 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.

Example: The sac (1 2 4 8 16 17 32 64 128 256 512 1024 2048 4096 4160 4164 8328 12492 12509) is the union of (1 2 4 8 16 17) and (1 2 4 8 16 32 64 128 256 512 1024 2048 4096 4160 4164 8328 12492).

b) True for $n<14759$ (by exhaustive search): every sac of 14759 starts with (1 2 3).

c) $\implies$ true for $n<14759$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.