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

1, 0, 1, 1, 2, 1, 2, 1, 6, 2, 2, 1, 36, 1, 2, 2, 56, 1, 90, 1, 201, 2, 2, 1, 4725, 2, 2, 20, 1085, 1, 15778, 1, 5272, 2, 2, 2, 476355, 1, 2, 2, 270084, 1, 302265, 1, 35324, 3910, 2, 1, 67279595, 2, 14047, 2, 219528, 1, 5863044, 2, 14362998, 2, 2, 1, 47466605656, 1, 2, 35662, 47350056, 2, 119762253, 1, 9479643

Offset: 0

Author

Ilya Gutkovskiy, Mar 27 2017

Keywords

• nonn

Examples

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

Links

• Robert Israel, Table of n, a(n) for n = 0..5039
• Eric Weisstein's World of Mathematics, Prime Power
• Index entries for sequences related to compositions

Crossrefs

Cf. A066882, A100346, A246655, A280195, A284289.

Programs

Maple

F:= proc(n) local f,G;
      G:= 1/(1 - add(add(x^(f[1]^j),j=1..f[2]),f = ifactors(n)[2]));
      coeff(series(G,x,n+1),x,n);
end proc:
map(F, [$0..100]); # Robert Israel, Mar 29 2017

Mathematica

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

Python

from sympy import divisors, primefactors
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if len(primefactors(x))==1]
    @cacheit
    def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)
    return b(n)
print([a(n) for n in range(71)]) # Indranil Ghosh, Aug 01 2017

Formula

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

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

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