A Brauer chain or star addition chain is an addition chain in which one of the summands is always the previous chain: that is,
- for each k>0: ak = ak-1 + aj for some j < k.
A Brauer number is one for which the Brauer chain is minimal.
Brauer proved that
- l*(2n−1) ≤ n − 1 + l*(n)
where l* is the length of the shortest star chain. For many values of n,and in particular for n ≤ 2500, they are equal: l(n) = l*(n). But Hansen showed that there are some values of n for which l(n) ≠ l*(n), such as n = 26106 + 23048 + 22032 + 22016 + 1 which has l*(n) = 6110, l(n) ≤ 6109.
Read more about this topic: Addition Chain
Famous quotes containing the word chain:
“By this unprincipled facility of changing the state as often, and as much, and in as many ways as there are floating fancies or fashions, the whole chain and continuity of the commonwealth would be broken. No one generation could link with the other. Men would become little better than the flies of a summer.”
—Edmund Burke (1729–1797)