A128998 Length of shortest addition-subtraction chain for n.

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 6, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 7, 7, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 9

Offset

1,3

Comments

Equivalently, the minimal total number of multiplications and divisions required to compute an n-th power. This is useful for exponentiation on, for example, elliptic curves where division is cheap (as proposed by Morain and Olivos, 1990). Addition-subtraction chains are also defined for negative n. Various bounds and a rules to construct a(n) up to n=42 can be found in Volger (1985).

a(n) < A003313(n) for n in A229624. - T. D. Noe, May 02 2007

Links

Table of n, a(n) for n=1..87.

Jens Groth and Victor Shoup, Fast batched asynchronous distributed key generation, Cryptology ePrint Archive, 2023. See p. 31.

F. Morain and J. Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Informatique theoretique et application, vol. 24 (1990), pp. 531-543.

Hugo Volger, Some results on addition/subtraction chains, Information Processing Letters, Vol. 20 (1985), pp. 155-160.

Index to sequences related to the complexity of n

Example

a(31) = 6 because 31 = 2^5 - 1 and 2^5 can be produced by 5 additions (5 doublings) starting with 1.

Crossrefs

Cf. A003313.

Sequence in context: A259847 A259103 A334200 * A137813 A003313 A353058

Adjacent sequences: A128995 A128996 A128997 * A128999 A129000 A129001

Keyword

nonn,nice

Author

Steven G. Johnson (stevenj(AT)math.mit.edu), May 01 2007

Extensions

More terms from T. D. Noe, May 02 2007

Status

approved