A284463 Number of compositions (ordered partitions) of n into prime divisors of n.

1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 12, 1, 2, 2, 1, 1, 65, 1, 23, 2, 2, 1, 351, 1, 2, 1, 38, 1, 15778, 1, 1, 2, 2, 2, 10252, 1, 2, 2, 1601, 1, 302265, 1, 80, 750, 2, 1, 299426, 1, 13404, 2, 107, 1, 1618192, 2, 5031, 2, 2, 1, 707445067, 1, 2, 2398, 1, 2, 119762253, 1, 173, 2, 39614048, 1, 255418101, 1, 2, 154603

Offset: 0

Author

Ilya Gutkovskiy, Mar 27 2017

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000
• Index entries for sequences related to compositions

Crossrefs

Cf. A000040, A014652, A023360, A066882, A100346.

Programs

Maple

a:= proc(n) option remember; local b, l;
      l, b:= numtheory[factorset](n),
      proc(m) option remember; `if`(m=0, 1,
         add(`if`(j>m, 0, b(m-j)), j=l))
      end; b(n)
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 28 2017

Mathematica

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

Python

from sympy import divisors, isprime
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if isprime(x)]
    @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(101)]) # Indranil Ghosh, Aug 01 2017, after Maple code

Formula

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

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

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