

A128998


Length of shortest additionsubtraction chain for n.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Equivalently, the minimal total number of multiplications and divisions required to compute an nth power. This is useful for exponentiation on, for example, elliptic curves where division is cheap (as proposed by Morain and Olivos, 1990). Additionsubtraction 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


REFERENCES

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


LINKS

Table of n, a(n) for n=1..87.
F. Morain and J. Olivos, Speeding up the computations on an elliptic curve using additionsubtraction chains, RAIRO Informatique theoretique et application, vol. 24 (1990), pp. 531543.
Index to sequences related to the complexity of n


EXAMPLE

For 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: A208280 A139141 A122953 * A137813 A003313 A117497
Adjacent sequences: A128995 A128996 A128997 * A128999 A129000 A129001


KEYWORD

nonn,nice,changed


AUTHOR

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


EXTENSIONS

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


STATUS

approved



