addition chain
An addition chain is a sequence
of integers of length such that each term for (with ) is the sum of two previous terms in at least one way. In the sum it is not required that . 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 .
There are various subclassifications of addition chains, such as the Lucas chains. A Mian-Chowla sequence
is an addition chain with the restriction
that each term is the sum of two previous terms in only one way. The length may be infinite
, and thus the Fibonacci sequence
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 |