A229624 -id:A229624 - cp's OEIS frontend

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

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

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

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

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.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5.
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

Cf. A003313.

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

cp's OEIS Frontend

A128998 Length of shortest addition-subtraction chain for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions