A005766 a(n) = cost of minimal multiplication-cost addition chain for n.

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

Offset: 1

Author

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

Keywords

• nonn

References

• 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, A. C.-C. Yao, F. F. Yao, Addition chains with multiplicative cost Discrete Math. 23 (1978), 115-119.
• 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

Crossrefs

Partial sums of A089265.

Programs

Mathematica

a[n_] := Sum[v = IntegerExponent[k, 2]; v + k/2^v - 1, {k, 1, n}];
Array[a, 55] (* Jean-François Alcover, Feb 28 2019 *)

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)

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

Extensions

More terms from Ralf Stephan, May 04 2003