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
    @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

2

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