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

Author

N. J. A. Sloane, Mar 19 2003

Keywords

• nonn

Examples

			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)
		

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]

Crossrefs

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

See also A136013, A333979.

Programs

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

PARI

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

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