| Displaying 1-5 of 5 results found.
page
1
Number of partitions of n into prime divisors of n.
+10
11
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
FORMULA
Coefficient of x^n in expansion of 1/Product_{d is prime divisor of n} (1-x^d). - Vladeta Jovovic, Apr 11 2004
MAPLE
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:
MATHEMATICA
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 *)
CROSSREFS
Main diagonal of A107329 (for n>=1).
Number of partitions of n into prime power divisors of n (not including 1).
+10
5
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
FORMULA
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.
EXAMPLE
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].
MAPLE
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:
MATHEMATICA
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 *)
Number of partitions of n into its nonprime power divisors with at least one part of size 1.
+10
3
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
PROG
(PARI)
\\ 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
(PARI) \\ For an efficient program to compute large numbers of terms, see PARI program included in the Links-section.
Number of partitions of n into its divisors that are powers of primes ( A000961) with at least one part of size 1.
+10
3
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
PROG
(PARI)
\\ 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
(PARI) \\ 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
Number of compositions (ordered partitions) of n into prime divisors of n.
+10
3
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
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:
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
Search completed in 0.006 seconds
| 