%I A128998
%S A128998 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,
%T A128998 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,
%U A128998 8,7,8,8,8,8,8,8,8,7,8,8,8,8,8,8,9
%N A128998 Length of shortest addition-subtraction chain for n.
%C A128998 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 A128998 a(n) < A003313(n) for n=31, 47, 62, 63, 71, 79. - T. D. Noe (noe(AT)sspectra.com), 
               May 02 2007
%D A128998 Hugo Volger, Some results on addition/subtraction chains, Information 
               Processing Letters, Vol. 20 (1985), pp. 155-160.
%H A128998 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.
%e A128998 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 A128998 Cf. A003313.
%Y A128998 Sequence in context: A117119 A139141 A122953 this_sequence A137813 A003313 
               A117497
%Y A128998 Adjacent sequences: A128995 A128996 A128997 this_sequence A128999 A129000 
               A129001
%K A128998 more,nonn,nice
%O A128998 1,3
%A A128998 Steven G. Johnson (stevenj(AT)math.mit.edu), May 01 2007
%E A128998 More terms from T. D. Noe (noe(AT)sspectra.com), May 02 2007