↑ arvau

Wikipedia / Addition chain

In mathematics, an addition chain for computing a positive integer can be given by a sequence of natural numbers starting with 1 and ending with , such that each number in the sequence is the sum of two of the previous numbers. The length of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers.

Examples

As an example: (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since

  1. 2 = 1 + 1

  2. 3 = 2 + 1

  3. 6 = 3 + 3

  4. 12 = 6 + 6

  5. 24 = 12 + 12

  6. 30 = 24 + 6

  7. 31 = 30 + 1

Addition chains can be used for addition-chain exponentiation. This method allows exponentiation with integer exponents to be performed using a number of multiplications equal to the length of an addition chain for the exponent. For instance, the addition chain for 31 leads to a method for computing the 31st power of any number using only seven multiplications, instead of the 30 multiplications that one would get from repeated multiplication, and eight multiplications with exponentiation by squaring:

  1. 2 = ×

  2. 3 = 2 ×

  3. 6 = 3 × 3

  4. 12 = 6 × 6

  5. 24 = 12 × 12

  6. 30 = 24 × 6

  7. 31 = 30 ×

Methods for computing addition chains

Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete. There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques are known to calculate relatively short chains that are not always optimal.

One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring and then adding one.

The factor method for finding addition chains is based on the prime factorization. The ideas of the factor method and binary method can be combined into Brauer's m-ary method, and then adding the remainder. Additional refinements of these ideas lead to a family of methods called sliding window methods.

Chain length

is the Hamming weight.

, observed by Knuth.,, and so on .

Brauer chain

A Brauer chain or star addition chain is an addition chain in which each of the sums used to calculate its numbers uses the immediately previous number. A Brauer number is a number for which a Brauer chain is optimal.

Brauer proved that

where is the length of the shortest star chain., they are equal: . But Hansen showed that there are some values of n for which , such as which has . The smallest such n is 12509.

Scholz conjecture

The Scholz conjecture (sometimes called the Scholz–Brauer or Brauer–Scholz conjecture), named after Arnold Scholz and Alfred T. Brauer), is a conjecture from 1937 stating that

are Hansen (while 5784689 is not)..

See also

References