|
|
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
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
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
|
|
MATHEMATICA
|
a[n_] := Sum[v = IntegerExponent[k, 2]; v + k/2^v - 1, {k, 1, n}];
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|