# Infinite Addition Chains

An **infinite addition chain** is an infinite sequence *(a*_{i})_{i} of strictly monotonic increasing natural numbers *a*_{i} starting with 1, such that each element of this sequence except the first, *a*_{0}=1, is the sum of two (not necessarily different) previous elements.

We call such an infinite addition chain **minimal**, if it contains an infinite subsequence *(a*_{ih})_{h} such that for each element *a*_{ih} of this subsequence *ℓ(a*_{ih}) = i_{h} holds -- i.e. it contains a shortest addition chain for each *a*_{ih}.

Furthermore we call a minimal infinite addition chain **unbounded minimal** if *s(a*_{ih}) is unbounded when *h* tends to infinity.
On the other hand, if *s(a*_{ih}) is bounded, then exists an index, say *i*_{b}, such that all steps in this minimal infinite addition chain with indices *j > i*_{b} are double steps and therefore *ℓ(a*_{j})=j.

Finally here are two examples for infinite addition chains; one for a non unbounded minimal: *1,2,4,8,...,2*^{n},...

and one for a unbounded minimal:
*1,2,3,6,12,15,30,60,120,240,255,510,...,2*^{n}(2^{2m}-1),... with * n <= 2*^{m}.
The last example is only a conjectural-to-be unbounded minimal addition chain. To the author's knowledge there is no proved-to-be unbounded minimal addition chain known until today (september 2016).

An unbounded minimal addition chain is given by:
*1,2,4,5,8,16,32,64,69,128,...* such that the next term is either a doublestep or a doubling of the previous-to-previous element or a new smallstep *2*^{2i-2} for every positive index *i*.
For these numbers *n(k)=∑*^{k}_{i=1} 2^{2i-2} must hold *ℓ(n)=λ(n)+ν(n)-1*
because their bits at index *2*^{i}-2 are spaced sufficient increasingly far apart such that they can't be generated by carries of less than *s(n)=ν(n)-1=k-1* smallsteps.
Proof idea: *s* smallsteps can generate at most *2*^{s} bits from a single bit and thus could generate a further bit by their cummulated carries at most *2*^{s}-1 indices higher.

Remark: The same argument/proof works also for numbers *n(k)=∑*^{k}_{i=0} 2^{2i-1} respectively the infinite addition chain
*1,2,3,4,8,11,16,32,64,128,139,256,...*.

Achim Flammenkamp

Last update: 2020-05-25 23:15:44 UTC+2