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

Author

Ralf Stephan, Feb 13 2004

Keywords

• nonn
• easy

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.

Crossrefs

Cf. A006581, A000292, A007814.

Programs

Mathematica

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

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

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).