login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A128998 Length of shortest addition-subtraction chain for n. 2
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).

a(n) < A003313(n) for n in A229624. - T. D. Noe, May 02 2007

REFERENCES

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

LINKS

Table of n, a(n) for n=1..87.

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.

Index to sequences related to the complexity of n

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: A208280 A139141 A122953 * A137813 A003313 A117497

Adjacent sequences:  A128995 A128996 A128997 * A128999 A129000 A129001

KEYWORD

nonn,nice

AUTHOR

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

EXTENSIONS

More terms from T. D. Noe, May 02 2007

STATUS

approved

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

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

Last modified November 23 09:53 EST 2014. Contains 249840 sequences.