|
| |
|
|
A128998
|
|
Length of shortest addition-subtraction chain for n.
|
|
0
|
|
|
|
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 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=31, 47, 62, 63, 71, 79. - T. D. Noe, May 02 2007
|
|
|
REFERENCES
|
Hugo Volger, Some results on addition/subtraction chains, Information Processing Letters, Vol. 20 (1985), pp. 155-160.
|
|
|
LINKS
|
Table of n, a(n) for n=1..87.
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.
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
|
more,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
|
| |
|
|
