A284289 Number of partitions of n into prime power divisors of n (not including 1).

1, 0, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 7, 1, 2, 2, 10, 1, 7, 1, 10, 2, 2, 1, 34, 2, 2, 5, 13, 1, 21, 1, 36, 2, 2, 2, 72, 1, 2, 2, 73, 1, 28, 1, 19, 13, 2, 1, 249, 2, 10, 2, 22, 1, 50, 2, 127, 2, 2, 1, 419, 1, 2, 17, 202, 2, 42, 1, 28, 2, 43, 1, 1260, 1, 2, 13, 31, 2, 49, 1, 801, 23, 2, 1, 774, 2, 2, 2, 280, 1, 608

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Prime Power

Index entries for related partition-counting sequences

Formula

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

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

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

Example

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

Maple

with(numtheory):
a:= proc(n) option remember; local b, l; l, b:= sort(
      [select(x-> nops(ifactors(x)[2])=1, divisors(n))[]]),
      proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
        b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
      end; b(n, nops(l))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 30 2017

Mathematica

Table[d = Divisors[n]; Coefficient[Series[Product[1/(1 - Boole[PrimePowerQ[d[[k]]]] x^d[[k]]), {k, Length[d]}], {x, 0, n}], x, n], {n, 0, 90}] (* or *)
a[0]=1; a[1]=0; a[n_] := Length@IntegerPartitions[n, All, Join @@ (#[[1]]^Range[#[[2]]] & /@ FactorInteger[n])]; a /@ Range[0, 90] (* Giovanni Resta, Mar 25 2017 *)

Crossrefs

Cf. A014652, A018818, A023894, A066882, A225244, A211110, A246655.

Sequence in context: A292504 A281118 A349137 * A111588 A070972 A180229

Adjacent sequences: A284286 A284287 A284288 * A284290 A284291 A284292

Keyword

nonn

Author

Ilya Gutkovskiy, Mar 24 2017

Status

approved