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,5

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

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.

Example

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

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

Prog

(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

Crossrefs

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

Sequence in context: A130675 A319118 A163820 * A327899 A276157 A169593

Adjacent sequences: A284462 A284463 A284464 * A284466 A284467 A284468

Keyword

nonn

Author

Ilya Gutkovskiy, Mar 27 2017

Status

approved