This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A128998 #23 Feb 19 2025 11:57:05 %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, %T A128998 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 A128998 8,8,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 in A229624. - _T. D. Noe_, May 02 2007 %H A128998 Jens Groth and Victor Shoup, <a href="https://eprint.iacr.org/2023/1175">Fast batched asynchronous distributed key generation</a>, Cryptology ePrint Archive, 2023. See p. 31. %H A128998 F. Morain and J. Olivos, <a href="https://doi.org/10.1051/ita/1990240605311">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 A128998 Nathan Mihm, <a href="https://www-users.cse.umn.edu/~reiner/HonorsTheses/Mihm_thesis.pdf">Optimal Addition-Subtraction Chains</a>, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5. %H A128998 Hugo Volger, <a href="https://doi.org/10.1016/0020-0190(85)90085-7">Some results on addition/subtraction chains</a>, Information Processing Letters, Vol. 20 (1985), pp. 155-160. %H A128998 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a> %e A128998 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. %K A128998 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_, May 02 2007