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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Index entries for sequences related to compositions

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.

Example

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

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

Prog

(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

Crossrefs

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

Sequence in context: A175456 A122377 A293900 * A169758 A175933 A175940

Adjacent sequences: A284460 A284461 A284462 * A284464 A284465 A284466

Keyword

nonn

Author

Ilya Gutkovskiy, Mar 27 2017

Status

approved