A331925 Number of compositions (ordered partitions) of n into distinct prime powers (including 1).

1, 1, 1, 3, 3, 5, 10, 11, 17, 19, 48, 49, 62, 85, 120, 258, 175, 337, 464, 631, 646, 932, 1686, 1991, 2122, 2455, 4118, 4545, 6010, 6481, 13302, 14383, 16177, 16912, 26454, 32024, 35468, 42389, 57334, 107708, 73830, 125629, 142560, 200377, 172752, 244624

Offset: 0

Author

Ilya Gutkovskiy, Feb 01 2020

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A000961, A023893, A106244, A219107, A280543, A331847.

Programs

Maple

N:= 50: # for a(0)..a(N)
P:= select(isprime, [2,seq(i,i=3..N,2)]):
PP:= sort([1,seq(seq(p^j, j = 1 .. ilog[p](N)),p=P)]):G:= 1:
for s in PP do
  G:= G + series(G*x*y^s,y,N+1);
od:
G:= convert(G,polynom):
T:= add(coeff(G,x,i)*i!,i=0..N):
seq(coeff(T,y,i),i=0..N); # Robert Israel, Jun 28 2024