A284839 Number of compositions (ordered partitions) of n into prime power divisors of n (including 1).

1, 1, 2, 2, 6, 2, 24, 2, 56, 20, 128, 2, 1490, 2, 741, 449, 5272, 2, 36901, 2, 81841, 3320, 29966, 2, 4135004, 572, 200389, 26426, 5452795, 2, 110187694, 2, 47350056, 226019, 9262156, 51885, 10783889706, 2, 63346597, 2044894, 14064551462, 2, 109570982403, 2, 35537376325, 470326038, 2972038874, 2

Offset: 0

Author

Ilya Gutkovskiy, Apr 03 2017

Keywords

• nonn

Examples

			a(4) = 6 because 4 has 3 divisors {1, 2, 4} and all are prime powers therefore we have [4], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2] and [1, 1, 1, 1].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Eric Weisstein's World of Mathematics, Prime Power
• Index entries for sequences related to compositions

Crossrefs

Cf. A000961, A066882, A100346, A284465.

Programs

Maple

with(numtheory):
a:= proc(n) local d, b; d, b:= select(x->
      nops(factorset(x))<2, divisors(n)),
      proc(n) option remember; `if`(n=0, 1,
        add(`if`(j>n, 0, b(n-j)), j=d))
      end: b(n)
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Apr 15 2017

Mathematica

Table[d = Divisors[n]; Coefficient[Series[1/(1 - x - Sum[Boole[PrimePowerQ[d[[k]]]] x^d[[k]], {k, Length[d]}]), {x, 0, n}], x, n], {n, 0, 47}]

Formula

a(n) = [x^n] 1/(1 - x - Sum_{p^k|n, p prime, k>=1} x^(p^k)).

a(n) = 2 if n is a prime.