A281811 Expansion of Sum_{i>=0} x^(2^i) / (1 - Sum_{j>=0} x^(2^j))^2.

1, 3, 7, 16, 34, 71, 143, 286, 562, 1096, 2114, 4054, 7720, 14631, 27591, 51834, 97018, 181030, 336810, 625062, 1157288, 2138200, 3942858, 7257830, 13338024, 24474978, 44848232, 82073852, 150016328, 273893503, 499534495, 910161570, 1656786466, 3013237398, 5475710770, 9942780954, 18040712384, 32711070838

Offset

1,2

Comments

Total number of parts in all compositions (ordered partitions) of n into powers of 2 (A000079).

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..4000

Index entries for sequences related to compositions

Formula

G.f.: Sum_{i>=0} x^(2^i) / (1 - Sum_{j>=0} x^(2^j))^2.

a(n) ~ c * n / r^n, where r = 0.566123792684559918241681653033264449147... is the root of the equation Sum_{j>=0} r^(2^j) = 1 and c = 0.34432689951558638915900387175922521737229978512101795819134... . - Vaclav Kotesovec, Feb 17 2017

Example

a(4) = 16 because we have [4], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1] and 1 + 2 + 3 + 3 + 3 + 4 = 16.

Maple

b:= proc(n) option remember; `if`(n=0, [1, 0], add(
      (p-> p+[0, p[1]])(b(n-2^j)), j=0..ilog2(n)))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=1..55);  # Alois P. Heinz, Aug 07 2019

Mathematica

nmax = 38; Rest[CoefficientList[Series[Sum[x^2^i, {i, 0, nmax}]/(1 - Sum[x^2^j, {j, 0, nmax}])^2, {x, 0, nmax}], x]]
nmax = 40; Rest[CoefficientList[Series[Sum[x^(2^i), {i, 0, Floor[Log[nmax]/Log[2]] + 1}]/(1 - Sum[x^(2^j), {j, 0, Floor[Log[nmax]/Log[2]] + 1}])^2, {x, 0, nmax}], x]] (* Vaclav Kotesovec, Feb 17 2017 *)

Crossrefs

Cf. A000079, A023359.

Sequence in context: A181893 A054455 A178455 * A238089 A335713 A026734

Adjacent sequences: A281808 A281809 A281810 * A281812 A281813 A281814

Keyword

nonn

Author

Ilya Gutkovskiy, Jan 30 2017

Status

approved