# addition chain

An addition chain^{} $a$ is a sequence^{} of integers of length $k$ such that each term ${a}_{i}$ for $$ (with ${a}_{0}=1$) is the sum of two previous terms in at least one way. In the sum ${a}_{m}+{a}_{n}$ it is not required that $m\ne n$. 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 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 |