A006520 Partial sums of A006519. (Formerly M2344)

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,2

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.

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

Mathematica

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

Prog

(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

Crossrefs

First differences of A022560.

Cf. A001620, A001787, A006519.

Sequence in context: A047460 A193532 A068056 * A054204 A050003 A002156

Adjacent sequences: A006517 A006518 A006519 * A006521 A006522 A006523

Keyword

nonn,easy

Author

N. J. A. Sloane, Simon Plouffe

Extensions

More terms from Benoit Cloitre, Dec 17 2002

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

Status

approved