Addition Chain - Brauer Chain

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:

    Nae living man I’ll love again,
    Since that my lovely knight is slain.
    Wi ae lock of his yellow hair
    I’ll chain my heart for evermair.
    —Unknown. The Lament of the Border Widow (l. 25–28)