A331923 Number of compositions (ordered partitions) of n into distinct perfect powers.

1, 1, 0, 0, 1, 2, 0, 0, 1, 3, 2, 0, 2, 8, 6, 0, 1, 4, 6, 0, 2, 12, 24, 0, 2, 9, 8, 1, 8, 32, 30, 2, 7, 10, 32, 8, 11, 44, 150, 30, 34, 40, 18, 26, 20, 68, 78, 126, 56, 169, 80, 30, 40, 116, 294, 144, 162, 226, 182, 128, 66, 338, 348, 752, 199, 1048

Offset: 0

Author

Ilya Gutkovskiy, Feb 01 2020

Keywords

• nonn
• look

Examples

			a(17) = 4 because we have [16, 1], [9, 8], [8, 9] and [1, 16].
		

Links

• Robert Israel, Table of n, a(n) for n = 0..2600
• Index entries for sequences related to compositions

Crossrefs

Cf. A001597, A078635, A112345, A282500, A284171, A331844, A331845.

Programs

Maple

N:= 200: # for a(0)..a(N)
PP:= {1,seq(seq(b^i,i=2..floor(log[b](N))),b=2..floor(sqrt(N)))}:
G:= mul(1+t*x^p, p=PP):
F:= proc(n) local R, k, v;
  R:= normal(coeff(G, x, n));
  add(k!*coeff(R, t, k), k=1..degree(R, t))
end proc:
F(0):= 1:
map(F, [$0..N]); # Robert Israel, Feb 03 2020

Mathematica

M = 200;
PP = Join[{1}, Table[Table[b^i, {i, 2, Floor[Log[b, M]]}], {b, 2, Floor[ Sqrt[M]]}] // Flatten // Union];
G = Product[1 + t x^p, {p, PP}];
a[n_] := Module[{R, k, v}, R = SeriesCoefficient[G, {x, 0, n}]; Sum[k! SeriesCoefficient[R, {t, 0, k}], {k, 1, Exponent[R, t]}]];
a[0] = 1;
a /@ Range[0, M] (* Jean-François Alcover, Oct 25 2020, after Robert Israel *)