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