This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A128998 Length of shortest addition-subtraction chain for n. 0

%I

%S 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,

%T 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,

%U 8,8,8,7,8,8,8,8,8,8,8,7,8,8,8,8,8,8,9

%N Length of shortest addition-subtraction chain for n.

%C 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).

%C a(n) < A003313(n) for n=31, 47, 62, 63, 71, 79. - _T. D. Noe_, May 02 2007

%D Hugo Volger, Some results on addition/subtraction chains, Information Processing Letters, Vol. 20 (1985), pp. 155-160.

%H F. Morain and J. Olivos, <a href="ftp://ftp.inria.fr/INRIA/publication/Theses/TU-0144/ch4.ps">Speeding up the computations on an elliptic curve using addition-subtraction chains</a>, RAIRO Informatique theoretique et application, vol. 24 (1990), pp. 531-543.

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

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

%Y Cf. A003313.

%K more,nonn,nice

%O 1,3

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

%E More terms from _T. D. Noe_, May 02 2007

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .