3
$\begingroup$

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

  • 0
    I think your definition is missing something. Otherwise every $n$ has the single-element addition chain {$n$}.2012-04-13
  • 0
    @TonyK: thanks, fixed it.2012-04-13
  • 0
    Have you seen the database at http://wwwold.iit.cnr.it/staff/giovanni.resta/ac/ which contains addition chains up to 1024?2012-04-14
  • 0
    @Gerry, thanks for the link - I learned that Brauer is a synonym for star ;) The online resources I checked were https://oeis.org/A003313 and http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html.2012-04-15

1 Answers 1