addition chain

An addition chainMathworldPlanetmath a is a sequenceMathworldPlanetmath of integers of length k such that each term ai for 0<ik (with a0=1) is the sum of two previous terms in at least one way. In the sum am+an it is not required that mn. For example, 1, 2, 3, 5, 10, 20, 40, 80, is an addition chain of length 7: 3 is 1 + 2, 5 = 2 + 3, 10 = 5 + 5, and the rest have m=n.

There are various subclassifications of addition chains, such as the Lucas chainsMathworldPlanetmath. A Mian-Chowla sequenceMathworldPlanetmath is an addition chain with the restrictionPlanetmathPlanetmathPlanetmath that each term is the sum of two previous terms in only one way. The length may be infiniteMathworldPlanetmath, and thus the Fibonacci sequenceMathworldPlanetmath is an addition chain.

Title addition chain
Canonical name AdditionChain
Date of creation 2013-03-22 18:27:27
Last modified on 2013-03-22 18:27:27
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 4
Author PrimeFan (13766)
Entry type Definition
Classification msc 11B13