Infinite Addition Chains

An infinite addition chain is an infinite sequence (ai)i of strictly monotonic increasing natural numbers ai starting with 1, such that each element of this sequence except the first, a0=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 (aih)h such that for each element aih of this subsequence ℓ(aih) = ih holds -- i.e. it contains a shortest addition chain for each aih.
Furthermore we call a minimal infinite addition chain unbounded minimal if s(aih) is unbounded when h tends to infinity. On the other hand, if s(aih) is bounded, then exists an index, say ib, such that all steps in this minimal infinite addition chain with indices j > ib are double steps and therefore ℓ(aj)=j.
Finally here are two examples for infinite addition chains; one for a non unbounded minimal: 1,2,4,8,...,2n,...
and one for a unbounded minimal: 1,2,3,6,12,15,30,60,120,240,255,510,...,2n(22m-1),... with n <= 2m. 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 22i-2 for every positive index i. For these numbers n(k)=∑ki=1 22i-2 must hold ℓ(n)=λ(n)+ν(n)-1 because their bits at index 2i-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 2s bits from a single bit and thus could generate a further bit by their cummulated carries at most 2s-1 indices higher.
Remark: The same argument/proof works also for numbers n(k)=∑ki=0 22i-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