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:
“Loyalty to petrified opinions never yet broke a chain or freed a human soul in this worldand never will.”
—Mark Twain [Samuel Langhorne Clemens] (18351910)
Related Phrases
Related Words