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

:2 = 1 + 1

:3 = 2 + 1

:6 = 3 + 3

:12 = 6 + 6

:24 = 12 + 12

:30 = 24 + 6

: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:

:² = ×

:³ = ² ×

:⁶ = ³ × ³

:¹² = ⁶ × ⁶

:²⁴ = ¹² × ¹²

:³⁰ = ²⁴ × ⁶

:³¹ = ³⁰ ×

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. In this method, an addition chain for the number <math>n</math> is obtained recursively, from an addition chain for <math>n'=\lfloor n/2\rfloor</math>. If <math>n</math> is even, it can be obtained in a single additional sum, as <math>n=n'+n'</math>. If <math>n</math> is odd, this method uses two sums to obtain it, by computing <math>n-1=n'+n'</math> and then adding one.

One can obtain an addition chain for <math>2n</math> from an addition chain for <math>n</math> by including one additional sum <math>2n=n+n</math>, from which follows the inequality <math>l(2n)\le l(n)+1</math> on the lengths of the chains for <math>n</math> and <math>2n</math>. However, this is not always an equality,

as in some cases <math>2n</math> may have a shorter chain than the one obtained in this way. For instance, <math>l(382)=l(191)=11</math>, observed by Knuth. For many values of <math>n</math>, and in particular for <math>n<12509</math>, 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

:<math> l(2^n-1) \le n - 1 + l(n). </math>

This inequality is known to hold for all Hansen numbers, a generalization of Brauer numbers; Neill Clift checked by computer that all <math> n \le 5784688 </math> are Hansen (while 5784689 is not). Clift further verified that in fact <math> l(2^n-1) = n - 1 + l(n)</math> for all <math>n \le 64</math>.

See also

• Addition-subtraction chain
• Vectorial addition chain
• Lucas chain

References

External links

• . Note that the initial "1" is not counted (so element #1 in the sequence is 0).
• F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"