A006520 Partial sums of A006519.

1, 3, 4, 8, 9, 11, 12, 20, 21, 23, 24, 28, 29, 31, 32, 48, 49, 51, 52, 56, 57, 59, 60, 68, 69, 71, 72, 76, 77, 79, 80, 112, 113, 115, 116, 120, 121, 123, 124, 132, 133, 135, 136, 140, 141, 143, 144, 160, 161, 163, 164, 168, 169, 171, 172, 180, 181, 183, 184, 188, 189

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• easy

Comments

The subsequence of primes in this partial sum begins: 3, 11, 23, 29, 31, 59, 71, 79, 113, 163, 181. The subsequence of powers in this partial sum begins: 1, 4, 8, 9, 32, 49, 121, 144, 169. - Jonathan Vos Post, Feb 18 2010

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1001 [Jul 23 2013; offset adapted by _Georg Fischer_, Jan 27 2020]
• 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. 44.
• Victor Meally, Letter to N. J. A. Sloane, May 1975.
• Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
• Ralf Stephan, Table of generating functions.

Crossrefs

First differences of A022560.

Cf. A001620, A001787, A006519, A136013, A159699.

Programs

Mathematica

Table[ 2^IntegerExponent[n, 2], {n, 1, 70}] // Accumulate (* Jean-François Alcover, May 14 2013 *)

PARI

a(n)=sum(i=1,n,2^valuation(i,2))

Python

def A006520(n): return sum(i&-i for i in range(1,n+1)) # Chai Wah Wu, Jul 14 2022

Formula

a(n)/(n*log(n)) is bounded. - Benoit Cloitre, Dec 17 2002

G.f.: (1/(x*(1-x))) * (x/(1-x) + Sum_{k>=1} 2^(k-1)*x^2^k/(1-x^2^k)). - Ralf Stephan, Apr 17 2003

a(n) = b(n+1), with b(2n) = 2b(n) + n, b(2n+1) = 2b(n) + n + 1. - Ralf Stephan, Sep 07 2003

a(2^k-1) = k*2^(k-1) = A001787(k) for any k > 0. - Rémy Sigrist, Jan 21 2021

a(n) ~ (1/(2*log(2)))*n*log(n) + (3/4 + (gamma-1)/(2*log(2)))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 15 2022

a(n) = A136013(n) + n = A159699(n) - n. - Alan Michael Gómez Calderón, Apr 13 2025

Extensions

More terms from Benoit Cloitre, Dec 17 2002

Offset changed to 1 by N. J. A. Sloane, Oct 18 2019