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,3

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

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.

Example

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].

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}]

Crossrefs

Cf. A000961, A066882, A100346, A284465.

Sequence in context: A324158 A196441 A130674 * A286376 A100346 A359004

Adjacent sequences: A284836 A284837 A284838 * A284840 A284841 A284842

Keyword

nonn

Author

Ilya Gutkovskiy, Apr 03 2017

Status

approved