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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Mar 19 2003
STATUS
approved