A284465 - OEIS

%I #17 Apr 21 2021 04:42:38

%S 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,

%T 1085,1,15778,1,5272,2,2,2,476355,1,2,2,270084,1,302265,1,35324,3910,

%U 2,1,67279595,2,14047,2,219528,1,5863044,2,14362998,2,2,1,47466605656,1,2,35662,47350056,2,119762253,1,9479643

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

%H Robert Israel, <a href="/A284465/b284465.txt">Table of n, a(n) for n = 0..5039</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimePower.html">Prime Power</a>

%H <a href="/index/Com#comp">Index entries for sequences related to compositions</a>

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

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

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

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

%p F:= proc(n) local f,G;

%p       G:= 1/(1 - add(add(x^(f[1]^j),j=1..f[2]),f = ifactors(n)[2]));

%p       coeff(series(G,x,n+1),x,n);

%p end proc:

%p map(F, [$0..100]); # _Robert Israel_, Mar 29 2017

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

%o (Python)

%o from sympy import divisors, primefactors

%o from sympy.core.cache import cacheit

%o @cacheit

%o def a(n):

%o     l=[x for x in divisors(n) if len(primefactors(x))==1]

%o     @cacheit

%o     def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)

%o     return b(n)

%o print([a(n) for n in range(71)]) # _Indranil Ghosh_, Aug 01 2017

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

%K nonn

%O 0,5

%A _Ilya Gutkovskiy_, Mar 27 2017