|
Search: id:A128998
|
|
|
| A128998 |
|
Length of shortest addition-subtraction chain for n. |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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 (noe(AT)sspectra.com), May 02 2007
|
|
REFERENCES
|
Hugo Volger, Some results on addition/subtraction chains, Information Processing Letters, Vol. 20 (1985), pp. 155-160.
|
|
LINKS
|
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.
|
|
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: A117119 A139141 A122953 this_sequence A137813 A003313 A117497
Adjacent sequences: A128995 A128996 A128997 this_sequence 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 (noe(AT)sspectra.com), May 02 2007
|
|
|
Search completed in 0.002 seconds
|
