A090889 Double partial sums of (n * its dyadic valuation).

0, 0, 2, 4, 14, 24, 40, 56, 96, 136, 186, 236, 310, 384, 472, 560, 712, 864, 1034, 1204, 1414, 1624, 1856, 2088, 2392, 2696, 3026, 3356, 3742, 4128, 4544, 4960, 5536, 6112, 6722, 7332, 8014, 8696, 9416, 10136, 10976, 11816, 12698, 13580

Offset

0,3

Comments

Hwang-Janson-Tsai paper, p. 39: "Note that the recurrence provided on OEIS for A090889 is incorrect (and the generating function misses a factor of 2)." - Michael De Vlieger, Oct 30 2022

Links

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 39.

Formula

a(0)=0, a(2n) = 2a(n) + 2a(n-1) + n(n+1)(2n+1)/3, a(2n+1) = 4a(n) + (2/3)*(n+1)(n+2)(n+3).

G.f.: (1/(1-x)^2) * Sum_{k>=0} 2^k*t^2/(1-t^2)^2 where t=x^2^k.

a(n) = A006581(n) + A000292(n-1).

Mathematica

{0}~Join~Accumulate@ Accumulate@ Array[# IntegerExponent[#, 2] &, 43] (* Michael De Vlieger, Oct 30 2022 *)

Prog

(PARI) a(n)=sum(k=1, n, bitand(k, n-k)+k*(n-k))
(PARI) a(n)=if(n<1, 0, if(n%2==0, 2*a(n/2)+2*a(n/2-1)+n/2*(n/2+1)*(n+1)/3, 4*a((n-1)/2)+2/3*((n-1)/2)*((n-1)/2+1)*((n-1)/2+2)))
(PARI) a(n)=sum(l=0, n, sum(k=0, l, k*valuation(k, 2)))
(Python)
def A090889(n): return (sum(k&n-k for k in range(1, n+1>>1))<<1)+(0 if n&1 else n>>1)+n*(n-1)*(n+1)//6 # Chai Wah Wu, May 08 2023

Crossrefs

Cf. A006581, A000292, A007814.

Sequence in context: A074716 A283290 A283379 * A350050 A096012 A261562

Adjacent sequences: A090886 A090887 A090888 * A090890 A090891 A090892

Keyword

nonn,easy

Author

Ralf Stephan, Feb 13 2004

Status

approved