|
|
A128998
|
|
Length of shortest addition-subtraction chain for n.
|
|
3
|
|
|
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).
|
|
LINKS
|
|
|
EXAMPLE
|
a(31) = 6 because 31 = 2^5 - 1 and 2^5 can be produced by 5 additions (5 doublings) starting with 1.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Steven G. Johnson (stevenj(AT)math.mit.edu), May 01 2007
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|