A014652 -id:A014652 - cp's OEIS frontend

A066882 Number of partitions of n into prime divisors of n.

1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 4, 1, 3, 2, 2, 1, 5, 1, 2, 1, 3, 1, 21, 1, 1, 2, 2, 2, 7, 1, 2, 2, 5, 1, 28, 1, 3, 4, 2, 1, 9, 1, 6, 2, 3, 1, 10, 2, 5, 2, 2, 1, 71, 1, 2, 4, 1, 2, 42, 1, 3, 2, 43, 1, 13, 1, 2, 6, 3, 2, 49, 1, 9, 1, 2, 1, 97, 2, 2, 2, 5, 1, 151, 2, 3, 2, 2, 2, 17, 1, 8

Offset: 0

Naohiro Nomoto, Jan 26 2002

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

Cf. A018818, A014652.

Main diagonal of A107329 (for n>=1).

with(numtheory):
a:= proc(n) local b, l; l:= sort([factorset(n)[]]):
      b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
             b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
          end; forget(b):
      b(n, nops(l))
    end:
seq(a(n), n=0..100); # Alois P. Heinz, Feb 05 2014

a[0] = 1; a[n_] := SeriesCoefficient[1/Product[1-x^d, {d, FactorInteger[n][[All, 1]]}], {x, 0, n}]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 30 2015, after Vladeta Jovovic *)

from sympy import factorint
from functools import cache
def A066882(n):
    @cache
    def b(m, i):
        if m == 0: return 1
        if i < 0: return 0
        return b(m, i-1) + (0 if l[i]>m else b(m-l[i], i))
    l = sorted(factorint(n))
    return b(n, len(l)-1)
print([A066882(n) for n in range(99)]) # Michael S. Branicky, Jan 08 2025 after Alois P. Heinz

Coefficient of x^n in expansion of 1/Product_{d is prime divisor of n} (1-x^d). - Vladeta Jovovic, Apr 11 2004

More terms from Sascha Kurz, Mar 23 2002

Corrected by Vladeta Jovovic, Apr 11 2004

A284289 Number of partitions of n into prime power divisors of n (not including 1).

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 7, 1, 2, 2, 10, 1, 7, 1, 10, 2, 2, 1, 34, 2, 2, 5, 13, 1, 21, 1, 36, 2, 2, 2, 72, 1, 2, 2, 73, 1, 28, 1, 19, 13, 2, 1, 249, 2, 10, 2, 22, 1, 50, 2, 127, 2, 2, 1, 419, 1, 2, 17, 202, 2, 42, 1, 28, 2, 43, 1, 1260, 1, 2, 13, 31, 2, 49, 1, 801, 23, 2, 1, 774, 2, 2, 2, 280, 1, 608

Offset: 0

Ilya Gutkovskiy, Mar 24 2017

nonn

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

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Prime Power
Index entries for related partition-counting sequences

Cf. A014652, A018818, A023894, A066882, A225244, A211110, A246655.

with(numtheory):
a:= proc(n) option remember; local b, l; l, b:= sort(
      [select(x-> nops(ifactors(x)[2])=1, divisors(n))[]]),
      proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
        b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
      end; b(n, nops(l))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Mar 30 2017

Table[d = Divisors[n]; Coefficient[Series[Product[1/(1 - Boole[PrimePowerQ[d[[k]]]] x^d[[k]]), {k, Length[d]}], {x, 0, n}], x, n], {n, 0, 90}] (* or *)
a[0]=1; a[1]=0; a[n_] := Length@IntegerPartitions[n, All, Join @@ (#[[1]]^Range[#[[2]]] & /@ FactorInteger[n])]; a /@ Range[0, 90] (* Giovanni Resta, Mar 25 2017 *)

a(n) = [x^n] Product_{p^k|n, p prime, k >= 1} 1/(1 - x^(p^k)).
a(n) = 1 if n is a prime.
a(n) = 2 if n is a semiprime.

A014649 Number of partitions of n into its nonprime power divisors with at least one part of size 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 6, 1, 1, 1, 2, 1, 15, 1, 1, 1, 1, 1, 16, 1, 1, 1, 6, 1, 21, 1, 2, 3, 1, 1, 26, 1, 5, 1, 2, 1, 18, 1, 6, 1, 1, 1, 238, 1, 1, 3, 1, 1, 31, 1, 2, 1, 31, 1, 139, 1, 1, 5, 2, 1, 37, 1, 26, 1, 1, 1, 414, 1, 1, 1, 6, 1, 612, 1, 2, 1, 1

Offset: 1

Olivier Gérard

nonn

Antti Karttunen, Table of n, a(n) for n = 1..20000
David A. Corneth & Antti Karttunen, PARI program

Cf. A014648, A014650, A014651, A014652, A066874.

\\ This is for computing a small number of terms:
nonprimepower_divisors_with1_reversed(n) = vecsort(select(d -> ((1==d) || !isprimepower(d)), divisors(n)), , 4);
partitions_into_with_trailing_ones(n, parts, from=1) = if(!n, 1, if(#parts<=(from+1), if(#parts == from, 1, (1+(n\parts[from]))), my(s=0); for(i=from, #parts, if(parts[i]<=n, s += partitions_into_with_trailing_ones(n-parts[i], parts, i))); (s)));
A014649(n) = partitions_into_with_trailing_ones(n-1, nonprimepower_divisors_with1_reversed(n)); \\ Antti Karttunen, Aug 23 2019

\\ For an efficient program to compute large numbers of terms, see PARI program included in the Links-section.

A014650 Number of partitions of n into its divisors that are powers of primes (A000961) with at least one part of size 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 5, 1, 6, 3, 8, 1, 27, 1, 11, 11, 26, 1, 43, 1, 63, 15, 17, 1, 215, 5, 20, 18, 114, 1, 226, 1, 166, 23, 26, 23, 734, 1, 29, 27, 728, 1, 422, 1, 261, 181, 35, 1, 2697, 7, 179, 35, 357, 1, 791, 35, 1729, 39, 44, 1, 6747, 1, 47, 325, 1626, 41, 996, 1, 594, 47, 1062, 1, 20345, 1, 56, 327, 735, 47, 1374, 1, 13485, 216, 62, 1

Offset: 1

Olivier Gérard

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
David A. Corneth, PARI program

Cf. A000961, A014648, A014649, A014651, A014652, A066874.

\\ This is for computing a small number of terms:
primepower_divisors_with1_reversed(n) = vecsort(select(d -> ((1==d) || isprimepower(d)), divisors(n)), , 4);
partitions_into_with_trailing_ones(n,parts,from=1) = if(!n,1, if(#parts<=(from+1), if(#parts == from,1,(1+(n\parts[from]))), my(s=0); for(i=from,#parts,if(parts[i]<=n, s += partitions_into_with_trailing_ones(n-parts[i],parts,i))); (s)));
A014650(n) = partitions_into_with_trailing_ones(n-1,primepower_divisors_with1_reversed(n)); \\ Antti Karttunen, Sep 10 2018

\\ For an efficient program to compute large numbers of terms, see David A. Corneth's PARI program included in the Links-section. - Antti Karttunen, Sep 12 2018

More terms from and the name clarified by Antti Karttunen, Sep 10 2018

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

Original entry on oeis.org

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

Ilya Gutkovskiy, Mar 27 2017

nonn

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

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

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

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

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

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

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.

cp's OEIS Frontend

A066882 Number of partitions of n into prime divisors of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A284289 Number of partitions of n into prime power divisors of n (not including 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A014649 Number of partitions of n into its nonprime power divisors with at least one part of size 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

A014650 Number of partitions of n into its divisors that are powers of primes (A000961) with at least one part of size 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula