| Displaying 1-10 of 10 results found.
page
1
Number of partitions of n into prime power parts (1 included); number of nonisomorphic Abelian subgroups of symmetric group S_n.
+10
48
1, 1, 2, 3, 5, 7, 10, 14, 20, 27, 36, 48, 63, 82, 105, 134, 171, 215, 269, 335, 415, 511, 626, 764, 929, 1125, 1356, 1631, 1953, 2333, 2776, 3296, 3903, 4608, 5427, 6377, 7476, 8744, 10205, 11886, 13818, 16032, 18565, 21463, 24768, 28536
FORMULA
G.f.: (Product_{p prime} Product_{k>=1} 1/(1-x^(p^k))) / (1-x).
EXAMPLE
The a(0) = 1 through a(6) = 10 partitions:
() (1) (2) (3) (4) (5) (33)
(11) (21) (22) (32) (42)
(111) (31) (41) (51)
(211) (221) (222)
(1111) (311) (321)
(2111) (411)
(11111) (2211)
(3111)
(21111)
(111111)
(End)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], Count[Map[Length, FactorInteger[#]], 1] == Length[#] &]], {n, 0, 35}] (* Geoffrey Critzer, Oct 25 2015 *) nmax = 50; Clear[P]; P[m_] := P[m] = Product[Product[1/(1-x^(p^k)), {k, 1, m}], {p, Prime[Range[PrimePi[nmax]]]}]/(1-x)+O[x]^nmax // CoefficientList[ #, x]&; P[1]; P[m=2]; While[P[m] != P[m-1], m++]; P[m] (* Jean-François Alcover, Aug 31 2016 *)
PROG
(PARI) lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (isprimepower(k), 1/(1-x^k), 1))/(1-x); for (n=0, m, print1(polcoeff(gf, n, t), ", ")); } \\ Michel Marcus, Mar 09 2013 (Python)
from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
@lru_cache(maxsize=None)
def c(n): return sum((p**(e+1)-p)//(p-1) for p, e in factorint(n).items())+1
return (c(n)+sum(c(k)* A023893(n-k) for k in range(1, n)))//n if n else 1 # Chai Wah Wu, Jul 15 2024
CROSSREFS
The multiplicative version (factorizations) is A000688. The version for just primes (not prime-powers) is A034891, strict A036497. These partitions are ranked by A302492. A001222 counts prime-power divisors.
A072233 counts partitions by sum and length.
Number of partitions of n into prime power parts (1 excluded).
+10
47
1, 0, 1, 1, 2, 2, 3, 4, 6, 7, 9, 12, 15, 19, 23, 29, 37, 44, 54, 66, 80, 96, 115, 138, 165, 196, 231, 275, 322, 380, 443, 520, 607, 705, 819, 950, 1099, 1268, 1461, 1681, 1932, 2214, 2533, 2898, 3305, 3768, 4285, 4872, 5530, 6267, 7094, 8022, 9060
FORMULA
G.f.: Prod(p prime, Prod(k >= 1, 1/(1-x^(p^k))))
EXAMPLE
The a(0) = 1 through a(9) = 7 partitions:
() . (2) (3) (4) (5) (33) (7) (8) (9)
(22) (32) (42) (43) (44) (54)
(222) (52) (53) (72)
(322) (332) (333)
(422) (432)
(2222) (522)
(3222)
(End)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], And@@PrimePowerQ/@#&]], {n, 0, 30}] (* Gus Wiseman, Jul 28 2022 *)
PROG
(PARI) is_primepower(n)= {ispower(n, , &n); isprime(n)}
lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (is_primepower(k), 1/(1-x^k), 1)); for (n=0, m, print1(polcoeff(gf, n, t), ", ")); }
(Python)
from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
@lru_cache(maxsize=None)
def c(n): return sum((p**(e+1)-p)//(p-1) for p, e in factorint(n).items())
return (c(n)+sum(c(k)* A023894(n-k) for k in range(1, n)))//n if n else 1 # Chai Wah Wu, Jul 15 2024
CROSSREFS
The multiplicative version (factorizations) is A000688, coprime A354911. Twice-partitions of this type are counted by A279784, factorizations A295935. These partitions are ranked by A355743. A001222 counts prime-power divisors.
A072233 counts partitions by sum and length.
Number of factorizations into distinct prime powers greater than 1.
+10
22
1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1
COMMENTS
a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).
FORMULA
Dirichlet g.f.: Product_{n is a prime power >1}(1 + 1/n^s).
Multiplicative with a(p^e) = A000009(e). Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{p prime} f(1/p) = 1.26020571070524171076..., where f(x) = (1-x) * Product_{k>=1} (1 + x^k). - Amiram Eldar, Oct 03 2023
EXAMPLE
The A000688(216) = 9 factorizations of 216 into prime powers are: (2*2*2*3*3*3)
(2*2*2*3*9)
(2*2*2*27)
(2*3*3*3*4)
(2*3*4*9)
(2*4*27)
(3*3*3*8)
(3*8*9)
(8*27)
Of these, the a(216) = 4 strict cases are:
(2*3*4*9)
(2*4*27)
(3*8*9)
(8*27)
(End)
MAPLE
local a, f;
if n = 1 then
1;
else
a := 1 ;
for f in ifactors(n)[2] do
end do:
end if;
MATHEMATICA
Table[Times @@ PartitionsQ[Last /@ FactorInteger[n]], {n, 99}] (* Arkadiusz Wesolowski, Feb 27 2017 *)
PROG
(Haskell)
a050361 = product . map a000009 . a124010_row
(PARI)
A000009(n, k=(n-!(n%2))) = if(!n, 1, my(s=0); while(k >= 1, if(k<=n, s += A000009(n-k, k)); k -= 2); (s));
CROSSREFS
This is the strict case of A000688. The case of primes (instead of prime-powers) is A008966, non-strict A000012. The non-strict additive version allowing 1's A023893, ranked by A302492. A001222 counts prime-power divisors.
A005117 lists all squarefree numbers.
A034699 gives maximal prime-power divisor.
Cf. A001970, A002110, A025487, A055887, A063834, A076610, A085970, A279786, A302590, A302601, A354911, A355742.
Number of integers ranging from 2 to n that are not prime-powers.
+10
17
0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 13, 14, 15, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 23, 24, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 32, 33, 33, 34, 34, 35, 36, 36, 37, 38, 38, 39, 40, 41, 41, 42, 42, 43
COMMENTS
For n > 2, a(n) gives the number of duplicate eliminations performed by the Sieve of Eratosthenes when sieving the interval [2, n]. - Felix Fröhlich, Dec 10 2016
EXAMPLE
The a(30) = 13 numbers: 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30. - Gus Wiseman, Jul 28 2022
MATHEMATICA
With[{nn = 75}, Table[n - Count[#, k_ /; k < n] - 1, {n, nn}] &@ Join[{1}, Select[Range@ nn, PrimePowerQ]]] (* Michael De Vlieger, Dec 11 2016 *)
PROG
(PARI) a(n) = my(i=0); forcomposite(c=4, n, if(!isprimepower(c), i++)); i \\ Felix Fröhlich, Dec 10 2016 (Python)
from sympy import primepi, integer_nthroot
def A085970(n): return n-1-sum(primepi(integer_nthroot(n, k)[0]) for k in range(1, n.bit_length())) # Chai Wah Wu, Aug 20 2024
CROSSREFS
The version not treating 1 as a prime-power is A356068. A000688 counts factorizations into prime-powers.
A001222 counts prime-power divisors.
Numbers whose prime indices are all prime-powers.
+10
14
1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25, 27, 31, 33, 35, 41, 45, 49, 51, 53, 55, 57, 59, 63, 67, 69, 75, 77, 81, 83, 85, 93, 95, 97, 99, 103, 105, 109, 115, 119, 121, 123, 125, 127, 131, 133, 135, 147, 153, 155, 157, 159, 161, 165, 171, 175, 177, 179, 187
COMMENTS
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. Also MM-numbers of multiset partitions into constant multisets, where the multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.
EXAMPLE
The terms together with their prime indices begin:
1: {}
3: {2}
5: {3}
7: {4}
9: {2,2}
11: {5}
15: {2,3}
17: {7}
19: {8}
21: {2,4}
23: {9}
25: {3,3}
27: {2,2,2}
31: {11}
33: {2,5}
35: {3,4}
41: {13}
45: {2,2,3}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], And@@PrimePowerQ/@primeMS[#]&]
CROSSREFS
The case of only primes (not all prime-powers) is A076610, strict A302590. Allowing prime index 1 gives A302492. These are the products of elements of A302493. Requiring n to be a prime-power gives A302601. These are the positions of 1's in A355741. A001222 counts prime-power divisors.
A034699 gives maximal prime-power divisor.
A355742 chooses a prime-power divisor of each prime index.
Number of integers ranging from 1 to n that are not prime-powers (1 is not a prime-power).
+10
8
1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 8, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 14, 15, 16, 17, 18, 18, 19, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 28, 29, 29, 30, 31, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 41, 42
EXAMPLE
The a(30) = 14 numbers: 1, 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30.
MATHEMATICA
Table[Length[Select[Range[n], !PrimePowerQ[#]&]], {n, 100}]
CROSSREFS
The version treating 1 as a prime-power is A085970. One more than the partial sums of A143731. A000688 counts factorizations into prime-powers.
A001222 counts prime-power divisors.
Number of factorizations of n into relatively prime prime-powers.
+10
7
1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 1, 0, 0, 2, 0, 2, 1, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 0, 1, 1, 1, 4, 0, 1, 1, 3, 0, 1, 0, 2, 2, 1, 0, 5, 0, 2, 1, 2, 0, 3, 1, 3, 1, 1, 0, 2, 0, 1, 2, 0, 1, 1, 0, 2, 1, 1, 0, 6, 0, 1, 2, 2, 1, 1, 0, 5, 0, 1, 0, 2, 1, 1, 1
FORMULA
a(n) = A000688(n) if n is nonprime, otherwise a(n) = 0.
EXAMPLE
The a(n) factorizations for n = 6, 12, 24, 36, 48, 72, 96:
2*3 3*4 3*8 4*9 3*16 8*9 3*32
2*2*3 2*3*4 2*2*9 2*3*8 2*4*9 3*4*8
2*2*2*3 3*3*4 3*4*4 3*3*8 2*3*16
2*2*3*3 2*2*3*4 2*2*2*9 2*2*3*8
2*2*2*2*3 2*3*3*4 2*3*4*4
2*2*2*3*3 2*2*2*3*4
2*2*2*2*2*3
MATHEMATICA
ufacs[s_, n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[ufacs[Select[s, Divisible[n/d, #]&], n/d], Min@@#>=d&]], {d, Select[s, Divisible[n, #]&]}]];
Table[Length[Select[ufacs[Select[Divisors[n], PrimePowerQ[#]&], n], GCD@@#<=1&]], {n, 100}]
CROSSREFS
For strict instead of relatively prime we have A050361, partitions A054685. For pairwise coprime instead of relatively prime we have A143731. The version for partitions instead of factorizations is A356067. A001222 counts prime-power divisors.
A289509 lists numbers whose prime indices are relatively prime.
A295935 counts twice-factorizations with constant blocks (type PPR).
A355743 lists numbers with prime-power prime indices, squarefree A356065.
Cf. A000837, A023893, A076610, A085970, A106244, A279784, A318721, A355737, A355742, A356064, A356066.
Numbers with a prime index other than 1 that is not a prime-power. Complement of A302492.
+10
6
13, 26, 29, 37, 39, 43, 47, 52, 58, 61, 65, 71, 73, 74, 78, 79, 86, 87, 89, 91, 94, 101, 104, 107, 111, 113, 116, 117, 122, 129, 130, 137, 139, 141, 142, 143, 145, 146, 148, 149, 151, 156, 158, 163, 167, 169, 172, 173, 174, 178, 181, 182, 183, 185, 188, 193
COMMENTS
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. These are numbers divisible by a prime number not of the form prime(q^k) where q is a prime number and k >= 1.
EXAMPLE
The terms together with their prime indices begin:
13: {6}
26: {1,6}
29: {10}
37: {12}
39: {2,6}
43: {14}
47: {15}
52: {1,1,6}
58: {1,10}
61: {18}
65: {3,6}
71: {20}
73: {21}
74: {1,12}
78: {1,2,6}
79: {22}
86: {1,14}
87: {2,10}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], !And@@PrimePowerQ/@DeleteCases[primeMS[#], 1]&]
CROSSREFS
Heinz numbers of the partitions counted by A023893. Allowing prime index 1 gives A356066. A001222 counts prime-power divisors.
A034699 gives the maximal prime-power divisor.
A355742 chooses a prime-power divisor of each prime index.
A355743 = numbers whose prime indices are prime-powers, squarefree A356065.
Numbers with a prime index that is not a prime-power. Complement of A355743.
+10
5
2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, 24, 26, 28, 29, 30, 32, 34, 36, 37, 38, 39, 40, 42, 43, 44, 46, 47, 48, 50, 52, 54, 56, 58, 60, 61, 62, 64, 65, 66, 68, 70, 71, 72, 73, 74, 76, 78, 79, 80, 82, 84, 86, 87, 88, 89, 90, 91, 92, 94, 96, 98, 100, 101
COMMENTS
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
EXAMPLE
The terms together with their prime indices begin:
2: {1}
4: {1,1}
6: {1,2}
8: {1,1,1}
10: {1,3}
12: {1,1,2}
13: {6}
14: {1,4}
16: {1,1,1,1}
18: {1,2,2}
20: {1,1,3}
22: {1,5}
24: {1,1,1,2}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], !And@@PrimePowerQ/@primeMS[#]&]
CROSSREFS
A001222 counts prime-power divisors.
A034699 gives the maximal prime-power divisor.
A355742 chooses a prime-power divisor of each prime index.
Number of integer partitions of n into relatively prime prime-powers.
+10
1
0, 0, 0, 0, 0, 1, 0, 3, 2, 5, 4, 11, 7, 18, 16, 26, 27, 43, 41, 65, 65, 92, 100, 137, 142, 194, 210, 270, 295, 379, 410, 519, 571, 699, 782, 947, 1046, 1267, 1414, 1673, 1870, 2213, 2465, 2897, 3230, 3757, 4210, 4871, 5427, 6265, 6997
EXAMPLE
The a(5) = 1 through a(12) = 7 partitions:
(32) . (43) (53) (54) (73) (74) (75)
(52) (332) (72) (433) (83) (543)
(322) (432) (532) (92) (552)
(522) (3322) (443) (732)
(3222) (533) (4332)
(542) (5322)
(722) (33222)
(3332)
(4322)
(5222)
(32222)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], And@@PrimePowerQ/@#&&GCD@@#==1&]], {n, 0, 30}]
CROSSREFS
The version for factorizations instead of partitions is A354911. A072233 counts partitions by sum and length.
A279784 counts twice-partitions where the latter partitions are constant.
A289509 lists numbers whose prime indices are relatively prime.
A355743 lists numbers with prime-power prime indices, squarefree A356065.
Search completed in 0.008 seconds
| 