A080277 - OEIS

%I #65 Aug 23 2024 02:09:29

%S 1,4,5,12,13,16,17,32,33,36,37,44,45,48,49,80,81,84,85,92,93,96,97,

%T 112,113,116,117,124,125,128,129,192,193,196,197,204,205,208,209,224,

%U 225,228,229,236,237,240,241,272,273,276,277,284,285,288,289,304,305,308

%N Partial sums of A038712.

%H Alois P. Heinz, <a href="/A080277/b080277.txt">Table of n, a(n) for n = 1..16383</a>

%H M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, <a href="http://arxiv.org/abs/1308.0403">Superpatterns and universal point sets</a>, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013-2014.

%H M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, <a href="http://dx.doi.org/10.7155/jgaa.00318">Superpatterns and universal point sets</a>, Journal of Graph Algorithms and Applications 18(2) (2014), 177-209.

%H Klaus Brockhaus, <a href="/A038712/a038712.gif">Illustration of A038712 and A080277</a>.

%H B. Dearden, J. Iiams, and J. Metzger, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Dearden/dearden3r.html">A Function Related to the Rumor Sequence Conjecture</a>, J. Int. Seq. 14 (2011), #11.2.3.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>. [ps file]

%H Ralf Stephan, <a href="/A080277/a080277.pdf">Table of generating functions</a>. [pdf file]

%F 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]

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

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

%F a(n) = n + 2*a(floor(n/2)). - _Vladeta Jovovic_, Aug 06 2003

%F From _Ralf Stephan_, Sep 07 2003: (Start)

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

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

%F 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

%F n log_2 n - 2n < a(n) <= n log_2 n + n [Bannister et al., 2013] - _David Eppstein_, Aug 31 2013

%F G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 - x)^2. - _Ilya Gutkovskiy_, Oct 30 2019

%F a(n) = A136013(2n). - _Pontus von Brömssen_, Sep 06 2020

%e From _Omar E. Pol_, Sep 10 2019: (Start)

%e Illustration of initial terms:

%e 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):

%e -----------------------------------

%e n  A038712(n)  a(n)       Diagram

%e -----------------------------------

%e .                         _ _ _ _

%e 1      1         1       |_| | | |

%e 2      3         4       |_ _| | |

%e 3      1         5       |_|   | |

%e 4      7        12       |_ _ _| |

%e 5      1        13       |_| |   |

%e 6      3        16       |_ _|   |

%e 7      1        17       |_|     |

%e 8     15        32       |_ _ _ _|

%e .

%e 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].

%e (End)

%p a:= proc(n) option remember;

%p       `if`(n=0, 0, a(n-1)+Bits[Xor](n, n-1))

%p     end:

%p seq(a(n), n=1..58);  # _Alois P. Heinz_, Feb 14 2023

%t Table[BitXor[n, n-1], {n, 1, 58}] // Accumulate (* _Jean-François Alcover_, Oct 24 2013 *)

%o (PARI) a(n) = fromdigits(Vec(Pol(binary(n<<1))'),2); \\ _Kevin Ryde_, Apr 29 2021

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

%Y See also A136013, A333979.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Mar 19 2003