An addition chain is a finite sequence of positive integers that starts at $1$, so that any element of the sequence is a sum of two previous elements. That is, it is a sequence $(a_1, \ldots, a_k)$ where $a_1 = 1$, and for each $i > 1$ there are $j, k < i$ such that $a_i = a_j + a_k$. An example of an addition chain is $$ (1, 2, 3, 6, 12, 15). $$ We call an addition chain that ends in $k$ an addition chain for $k$. We write $l(k)$ for the length of the shorted addition chain for $k$, not counting the 1 at the start of the sequence. Our example above shows that $l(15) \leq 5$; in fact $l(15) = 5$.

You can read much more about addition chains on Achim Flammenkamp's page or on Wikipedia.

Write $C(k)$ for the set of addition chains for $k$, and $s(c)$ for the length of a chain $c$ (again not counting the initial 1). Furthermore, we use the notation $c_1 \cup c_2$ informally to mean joining the chains $c_1, c_2$ while pruning repeat elements. Then we trivially have $$ l(k) = \min_{i < k \\c_1 \in C(i)\\ c_2 \in C(k - i)} s(c_1 \cup c_2) + 1. $$ Now in many cases, we will find that this minimum is not achieved if we restrict to $c_1, c_2$ such that $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$; to achieve maximal overlap, we may want a sequence for one of the summands which is suboptimal. My question is:

Is it possible that we need both subsequences to be suboptimal? That is, is the same minimum attained if we restrict to pairs $(c_1, c_2)$ such that at least one of $s(c_1) = l(i)$ and $s(c_2) = l(k - i)$ holds?

  • $\begingroup$ or mathworld ... $\endgroup$ – Roddy MacPhee Mar 25 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.