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:
“Oh yes, thats right. They chain up wild animals. Thats all I am, an animal.”
—John Elder [Anthony Hinds], British screenwriter, and Terence Fisher. Leon (Oliver Reed)
Related Phrases
Related Words