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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005766 a(n) = cost of minimal multiplication-cost addition chain for n.
(Formerly M2448)
5
0, 1, 3, 5, 9, 12, 18, 21, 29, 34, 44, 48, 60, 67, 81, 85, 101, 110, 128, 134, 154, 165, 187, 192, 216, 229, 255, 263, 291, 306, 336, 341, 373, 390, 424, 434, 470, 489, 527, 534, 574, 595, 637, 649, 693, 716, 762, 768, 816, 841, 891, 905, 957, 984, 1038 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

REFERENCES

R. L. Graham et al., Addition chains with multiplicative cost, Discrete Math., 23 (1978), 115-119.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n = 1..1000

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 21.

R. L. Graham et al., Addition chains with multiplicative cost [Cached copy]

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Index to sequences related to the complexity of n

FORMULA

a(2n)=a(n)+n^2, a(2n+1)=a(n)+n(n+2). - Ralf Stephan, May 04 2003

G.f. 1/(1-x) * sum(k>=0, x^2^(k+1)(1+2x^2^k-x^2^(k+1))/(1-x^2^(k+1))^2). - Ralf Stephan, Jul 27 2003

a(n) = sum(k=1, n, A007814(n) + 2*A025480(n-1)). - Ralf Stephan, Oct 30 2003

PROG

(PARI) a(n)=if(n<1, 0, if(n%2==0, a(n/2)+n^2/4, a((n-1)/2)+(n-1)*(n+3)/4))

(PARI) a(n)=sum(k=1, n, valuation(k, 2)+k/2^valuation(k, 2)-1)

CROSSREFS

Partial sums of A089265.

Sequence in context: A127722 A234813 A060419 * A211538 A247799 A265702

Adjacent sequences:  A005763 A005764 A005765 * A005767 A005768 A005769

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jeffrey Shallit, Robert G. Wilson v

EXTENSIONS

More terms from Ralf Stephan, May 04 2003

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 19 02:06 EST 2018. Contains 299330 sequences. (Running on oeis4.)