cp's OEIS Frontend

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

%I A284465 #18 Feb 16 2025 08:33:43
%S A284465 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 A284465 1085,1,15778,1,5272,2,2,2,476355,1,2,2,270084,1,302265,1,35324,3910,
%U A284465 2,1,67279595,2,14047,2,219528,1,5863044,2,14362998,2,2,1,47466605656,1,2,35662,47350056,2,119762253,1,9479643
%N A284465 Number of compositions (ordered partitions) of n into prime power divisors of n (not including 1).
%H A284465 Robert Israel, <a href="/A284465/b284465.txt">Table of n, a(n) for n = 0..5039</a>
%H A284465 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimePower.html">Prime Power</a>
%H A284465 <a href="/index/Com#comp">Index entries for sequences related to compositions</a>
%F A284465 a(n) = [x^n] 1/(1 - Sum_{p^k|n, p prime, k>=1} x^(p^k)).
%F A284465 a(n) = 1 if n is a prime.
%F A284465 a(n) = 2 if n is a semiprime.
%e A284465 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 A284465 F:= proc(n) local f,G;
%p A284465       G:= 1/(1 - add(add(x^(f[1]^j),j=1..f[2]),f = ifactors(n)[2]));
%p A284465       coeff(series(G,x,n+1),x,n);
%p A284465 end proc:
%p A284465 map(F, [$0..100]); # _Robert Israel_, Mar 29 2017
%t A284465 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 A284465 (Python)
%o A284465 from sympy import divisors, primefactors
%o A284465 from sympy.core.cache import cacheit
%o A284465 @cacheit
%o A284465 def a(n):
%o A284465     l=[x for x in divisors(n) if len(primefactors(x))==1]
%o A284465     @cacheit
%o A284465     def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)
%o A284465     return b(n)
%o A284465 print([a(n) for n in range(71)]) # _Indranil Ghosh_, Aug 01 2017
%Y A284465 Cf. A066882, A100346, A246655, A280195, A284289.
%K A284465 nonn
%O A284465 0,5
%A A284465 _Ilya Gutkovskiy_, Mar 27 2017