Find an Addition Chain
Enter a positive integer exponent. The calculator searches for a short addition chain using breadth-first search.
The chain starts at 1 and ends at the target exponent.
What Is an Addition Chain?
An addition chain is a sequence of positive integers that starts with 1. Every number after the first is obtained by adding two numbers that already appeared earlier in the sequence.
For example:
The terms satisfy:
3 = 2 + 1
5 = 3 + 2
10 = 5 + 5
15 = 10 + 5
Addition Chains and Exponentiation
Addition chains are closely connected to efficient exponentiation. Suppose we want to calculate x15.
The chain
can be translated into multiplication steps:
x³ = x² · x
x⁵ = x³ · x²
x¹⁰ = x⁵ · x⁵
x¹⁵ = x¹⁰ · x⁵
The exponent 15 is therefore reached using five multiplications after starting with x. The exact optimal chain can depend on the exponent and on which type of addition-chain problem is being considered.
Formal Definition
An addition chain for a positive integer n is a sequence
such that every term after the first can be written as the sum of two earlier terms:
where j, k < i.
Chain Length
The length of an addition chain is the number of additions used to reach the target.
For example:
reaches 16 in four additions.
Addition Chain Examples
| Target | Example Chain | Length |
|---|---|---|
| 2 | 1 → 2 | 1 |
| 4 | 1 → 2 → 4 | 2 |
| 8 | 1 → 2 → 4 → 8 | 3 |
| 10 | 1 → 2 → 4 → 5 → 10 | 4 |
| 15 | 1 → 2 → 3 → 5 → 10 → 15 | 5 |
| 16 | 1 → 2 → 4 → 8 → 16 | 4 |
Addition Chains vs. Binary Exponentiation
Binary exponentiation is a standard technique for computing powers efficiently. It uses the binary representation of an exponent and repeatedly squares intermediate results.
Addition chains provide a broader framework for describing exponentiation strategies.
Binary Method
Uses the binary representation of the exponent and repeated squaring, together with additional multiplications where needed.
Addition Chain
Allows each new exponent to be formed from any two earlier exponents, potentially producing shorter multiplication sequences for particular exponents.
Why Addition Chains Matter
Addition chains are useful because exponentiation can be expensive when performed through repeated multiplication. Instead of calculating x × x × x × ... one multiplication at a time, an addition chain organizes intermediate powers so that they can be reused.
This idea appears in areas including:
- Efficient exponentiation
- Computational number theory
- Algorithm design
- Modular arithmetic
- Cryptographic algorithms
- Large-integer computation
Addition chains are therefore a useful bridge between elementary arithmetic and algorithmic number theory.
Related Summe.org Calculators
Frequently Asked Questions
What is an addition chain?
An addition chain is a sequence beginning with 1 in which every subsequent number is the sum of two numbers that appeared earlier in the sequence.
What is an addition chain used for?
Addition chains are primarily studied as a way of organizing efficient exponentiation. A chain ending in n can describe a sequence of multiplications for calculating xn.
What is an example of an addition chain?
For 15, one addition chain is 1 → 2 → 3 → 5 → 10 → 15. Each term is formed by adding two earlier terms.
What is the shortest addition chain?
The shortest chain depends on the target integer. The minimum number of additions required to reach n is called the addition-chain length of n.
Are addition chains related to multiplication?
Yes. An addition in the exponent sequence corresponds to a multiplication of powers. For example, if a chain contains a = b + c, then xa can be obtained as xb × xc.
Are addition chains related to hyperoperations?
They are different mathematical concepts, but both are connected with repeated arithmetic operations. Addition chains focus on efficient exponentiation, while hyperoperations form a hierarchy of increasingly powerful arithmetic operations.