A339427 Number of compositions (ordered partitions) of n into an odd number of powers of 2.

0, 1, 1, 1, 4, 4, 9, 17, 26, 50, 88, 150, 274, 478, 841, 1497, 2634, 4650, 8234, 14518, 25654, 45340, 80040, 141414, 249822, 441192, 779422, 1376752, 2431772, 4295678, 7587761, 13402881, 23675186, 41819442, 73869802, 130483966, 230485902, 407130212, 719154602

Offset: 0

Author

Ilya Gutkovskiy, Dec 03 2020

Keywords

• nonn

Examples

			a(5) = 4 because we have [2, 2, 1], [2, 1, 2], [1, 2, 2] and [1, 1, 1, 1, 1].
		

Links

• Index entries for sequences related to compositions

Crossrefs

Cf. A000079, A023359, A040039, A166444, A339422, A339426.

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0, t,
      add(b(n-2^i, 1-t), i=0..ilog2(n)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Dec 03 2020

Mathematica

nmax = 38; CoefficientList[Series[(1/2) (1/(1 - Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]) - 1/(1 + Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}])), {x, 0, nmax}], x]

Formula

G.f.: (1/2) * (1 / (1 - Sum_{k>=0} x^(2^k)) - 1 / (1 + Sum_{k>=0} x^(2^k))).

a(n) = (A023359(n) - A339422(n)) / 2.

a(n) = -Sum_{k=0..n-1} A023359(k) * A339422(n-k).