|
%I #61 Feb 14 2023 18:33:12
%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
|
