A074330 a(n) = Sum_{k=1..n} 2^b(k) where b(k) denotes the number of 1's in the binary representation of k.

2, 4, 8, 10, 14, 18, 26, 28, 32, 36, 44, 48, 56, 64, 80, 82, 86, 90, 98, 102, 110, 118, 134, 138, 146, 154, 170, 178, 194, 210, 242, 244, 248, 252, 260, 264, 272, 280, 296, 300, 308, 316, 332, 340, 356, 372, 404, 408, 416, 424, 440, 448, 464, 480, 512, 520, 536

Offset: 1

Author

Benoit Cloitre, Oct 06 2002

Keywords

• easy
• nonn

Links

• Robert Israel, Table of n, a(n) for n = 1..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. 29.

Crossrefs

a(n) = A006046(n+1)-1. Cf. A080263.

Programs

Maple

f:= proc(n) option remember; if n::even then 2*procname(n/2-1)+procname(n/2)+2
  else 3*procname((n-1)/2)+2
  fi
end proc:
f(0):= 0:
map(f, [$1..100]); # Robert Israel, Oct 08 2020

Mathematica

b[n_] := IntegerDigits[n, 2] // Total;
a[n_] := 2^(b /@ Range[n]) // Total;
Array[a, 100] (* Jean-François Alcover, Aug 16 2022 *)

PARI

a(n)=sum(i=1,n,2^sum(k=1,length(binary(i)), component(binary(i),k)))

Formula

a(n+1)-a(n) = A001316(n)

From Ralf Stephan, Oct 07 2003: (Start)

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

G.f.: (1/(1-x)) * Product_{k>=0} (1 + 2x^2^k). (End)