A080277 Partial sums of A038712.

1, 4, 5, 12, 13, 16, 17, 32, 33, 36, 37, 44, 45, 48, 49, 80, 81, 84, 85, 92, 93, 96, 97, 112, 113, 116, 117, 124, 125, 128, 129, 192, 193, 196, 197, 204, 205, 208, 209, 224, 225, 228, 229, 236, 237, 240, 241, 272, 273, 276, 277, 284, 285, 288, 289, 304, 305, 308

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..16383

M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013-2014.

M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, Journal of Graph Algorithms and Applications 18(2) (2014), 177-209.

Klaus Brockhaus, Illustration of A038712 and A080277.

B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3.

Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.

Ralf Stephan, Table of generating functions. [ps file]

Ralf Stephan, Table of generating functions. [pdf file]

Formula

a(n) is conjectured to be asymptotic to n*log(n)/log(2). - Klaus Brockhaus, Mar 23 2003 [See Bannister et al., 2013. - N. J. A. Sloane, Nov 26 2013]

a(n) = Sum_{k=0..log_2(n)} 2^k*floor(n/2^k).

a(2^k) = (k+1)*2^k.

a(n) = n + 2*a(floor(n/2)). - Vladeta Jovovic, Aug 06 2003

From Ralf Stephan, Sep 07 2003: (Start)

a(1) = 1, a(2*n) = 2*a(n) + 2*n, a(2*n+1) = 2*a(n) + 2*n + 1.

G.f.: 1/(1-x) * Sum(k >= 0, 2^k*t/(1-t), t = x^2^k). (End)

Product_{n >= 1} (1 + x^(n*2^(n-1))) = (1 + x)*(1 + x^4)*(1 + x^12)*(1 + x^32)*... = 1 + Sum_{n >= 1} x^a(n) = 1 + x + x^4 + x^5 + x^12 + x^13 + .... Hence this sequence lists the numbers representable as a sum of distinct elements of A001787 = [1, 4, 12, ..., n*2^(n-1), ...]. Cf. A050292. See also A120385. - Peter Bala, Feb 02 2013

n log_2 n - 2n < a(n) <= n log_2 n + n [Bannister et al., 2013] - David Eppstein, Aug 31 2013

G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 - x)^2. - Ilya Gutkovskiy, Oct 30 2019

a(n) = A136013(2n). - Pontus von Brömssen, Sep 06 2020

Example

From Omar E. Pol, Sep 10 2019: (Start)
Illustration of initial terms:
a(n) is also the total area (or the total number of cells) in first n regions of an infinite diagram of compositions (ordered partitions) of the positive integers, where the length of the n-th horizontal line segment is equal to A001511(n), the length of the n-th vertical line segment is equal to A006519(n), and area of the n-th region is equal to A038712(n), as shown below (first eight regions):
-----------------------------------
n  A038712(n)  a(n)       Diagram
-----------------------------------
.                         _ _ _ _
1      1         1       |_| | | |
2      3         4       |_ _| | |
3      1         5       |_|   | |
4      7        12       |_ _ _| |
5      1        13       |_| |   |
6      3        16       |_ _|   |
7      1        17       |_|     |
8     15        32       |_ _ _ _|
.
The above diagram represents the eight compositions of 4: [1,1,1,1],[2,1,1],[1,2,1],[3,1],[1,1,2],[2,2],[1,3],[4].
(End)

Maple

a:= proc(n) option remember;
      `if`(n=0, 0, a(n-1)+Bits[Xor](n, n-1))
    end:
seq(a(n), n=1..58);  # Alois P. Heinz, Feb 14 2023

Mathematica

Table[BitXor[n, n-1], {n, 1, 58}] // Accumulate (* Jean-François Alcover, Oct 24 2013 *)

Prog

(PARI) a(n) = fromdigits(Vec(Pol(binary(n<<1))'), 2); \\ Kevin Ryde, Apr 29 2021

Crossrefs

Cf. A001787, A038712, A050292, A080333, A120385.

See also A136013, A333979.

Sequence in context: A323766 A330223 A325688 * A047608 A266725 A308783

Adjacent sequences: A080274 A080275 A080276 * A080278 A080279 A080280

Keyword

nonn

Author

N. J. A. Sloane, Mar 19 2003

Status

approved