A045782 -id:A045782 - cp's OEIS frontend

A050345 Number of ways to factor n into distinct factors with one level of parentheses.

1, 1, 1, 1, 1, 3, 1, 3, 1, 3, 1, 6, 1, 3, 3, 4, 1, 6, 1, 6, 3, 3, 1, 13, 1, 3, 3, 6, 1, 12, 1, 7, 3, 3, 3, 15, 1, 3, 3, 13, 1, 12, 1, 6, 6, 3, 1, 25, 1, 6, 3, 6, 1, 13, 3, 13, 3, 3, 1, 31, 1, 3, 6, 12, 3, 12, 1, 6, 3, 12, 1, 37, 1, 3, 6, 6, 3, 12, 1, 25, 4, 3, 1, 31, 3, 3, 3, 13, 1, 31, 3, 6, 3, 3

Offset: 1

Christian G. Bower, Oct 15 1999

nonn

First differs from A296120 at a(36) = 15, A296120(36) = 14. - Gus Wiseman, Apr 27 2025
Each "part" in parentheses is distinct from all others at the same level. Thus (3*2)*(2) is allowed but (3)*(2*2) and (3*2*2) are not.
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).

			12 = (12) = (6*2) = (6)*(2) = (4*3) = (4)*(3) = (3*2)*(2).
From _Gus Wiseman_, Apr 26 2025: (Start)
This is the number of ways to partition a factorization of n (counted by A001055) into a set of sets. For example, the a(12) = 6 choices are:
  {{2},{2,3}}
  {{2},{6}}
  {{3},{4}}
  {{2,6}}
  {{3,4}}
  {{12}}
(End)

R. J. Mathar, Table of n, a(n) for n = 1..2519

Cf. A050346-A050350. a(A002110)=A000258.
For multisets of multisets we have A050336.
For integer partitions we have a(p^k) = A050342(k), see A001970, A089259, A261049.
For normal multiset partitions see A116539, A292432, A292444, A381996, A382214, A382216.
The case of a unique choice (positions of 1) is A166684.
Twice-partitions of this type are counted by A358914, see A270995, A281113, A294788.
For sets of multisets we have A383310 (distinct products A296118).
For multisets of sets we have we have A383311, see A296119.
A001055 counts factorizations, strict A045778.
A050320 counts factorizations into squarefree numbers, distinct A050326.
A302494 gives MM-numbers of sets of sets.
A382077 counts partitions that can be partitioned into a sets of sets, ranks A382200.
A382078 counts partitions that cannot be partitioned into a sets of sets, ranks A293243.
Cf. A000009, A002865, A005117, A045782, A279785, A293511, A296120, A316439, A381441, A382201.

facs[n_]:=If[n<=1,{{}}, Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d, Rest[Divisors[n]]}]];
sps[{}]:={{}};sps[set:{i_,_}] := Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]] /@ Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort /@ (#/.x_Integer:>set[[x]])]& /@ sps[Range[Length[set]]]];
Table[Sum[Length[Select[mps[y], UnsameQ@@#&&And@@UnsameQ@@@#&]], {y,facs[n]}],{n,30}] (* Gus Wiseman, Apr 26 2025 *)

Dirichlet g.f.: Product_{n>=2}(1+1/n^s)^A045778(n).
a(n) = A050346(A025487^(-1)(A046523(n))), where A025487^(-1) is the inverse with A025487^(-1)(A025487(n))=n. - R. J. Mathar, May 25 2017
a(n) = A050346(A101296(n)). - Antti Karttunen, May 25 2017

A330977 Numbers whose number of factorizations into factors > 1 (A001055) is a power of 2.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 25, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 57, 58, 59, 61, 62, 63, 65, 67, 68, 69, 71, 72, 73, 74, 75, 76, 77, 79, 82, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Jan 07 2020

nonn

The complement starts: 8, 16, 24, 27, 30, 32, 36, 40.

			Factorizations of n = 1, 4, 12, 72:
  ()  (4)    (12)     (72)
      (2*2)  (2*6)    (8*9)
             (3*4)    (2*36)
             (2*2*3)  (3*24)
                      (4*18)
                      (6*12)
                      (2*4*9)
                      (2*6*6)
                      (3*3*8)
                      (3*4*6)
                      (2*2*18)
                      (2*3*12)
                      (2*2*2*9)
                      (2*2*3*6)
                      (2*3*3*4)
                      (2*2*2*3*3)

R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

The same for strict integer partitions is A331022.
Factorizations are A001055, with image A045782.
The least number with exactly n factorizations is A330973(n).
The least number with exactly 2^n factorizations is A330989(n).
Numbers whose inverse prime shadow belongs to this sequence are A330990.
Numbers with a prime number of factorizations are A330991.
Cf. A002033, A033833, A045778, A045783, A317145, A326028, A330972, A330976.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Select[Range[100],IntegerQ[Log[2,Length[facs[#]]]]&]

A330997 Sorted list containing the least number with each possible nonzero number of factorizations into distinct factors > 1.

Original entry on oeis.org

1, 6, 12, 24, 48, 60, 64, 96, 120, 144, 180, 210, 216, 240, 256, 288, 360, 384, 420, 432, 480, 512, 720, 840, 864, 900, 960, 1080, 1152, 1260, 1296, 1440, 1536, 1680, 1728, 1800, 2048, 2160, 2304, 2310, 2520, 2592, 2880, 3072, 3360, 3456, 3600, 3840, 4320

Offset: 1

Gus Wiseman, Jan 06 2020

nonn

			The strict factorizations of a(n) for n = 1..9.
  {}  6    12   24     48     60      64     96      120
      2*3  2*6  3*8    6*8    2*30    2*32   2*48    2*60
           3*4  4*6    2*24   3*20    4*16   3*32    3*40
                2*12   3*16   4*15    2*4*8  4*24    4*30
                2*3*4  4*12   5*12           6*16    5*24
                       2*3*8  6*10           8*12    6*20
                       2*4*6  2*5*6          2*6*8   8*15
                              3*4*5          3*4*8   10*12
                              2*3*10         2*3*16  3*5*8
                                             2*4*12  4*5*6
                                                     2*3*20
                                                     2*4*15
                                                     2*5*12
                                                     2*6*10
                                                     3*4*10
                                                     2*3*4*5

All terms belong to A025487.
Strict factorizations are A045778, with image A045779.
The unsorted version is A045780.
The non-strict version is A330972.
The least number with n strict factorizations is A330974.
Cf. A001055, A001222, A033833, A045782, A318286, A325238, A330935, A330973, A330975.

nn=1000;
strfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strfacs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[strfacs,nn];
Table[Position[nds,i][[1,1]],{i,First/@Gather[nds]}]

A330975 Numbers that are not the number of factorizations of n into distinct factors > 1 for any n.

Original entry on oeis.org

11, 13, 20, 23, 24, 26, 28, 29, 30, 35, 36, 37, 39, 41, 45, 47, 48, 49, 50, 51, 53, 58, 60, 62, 63, 65, 66, 68, 69, 71, 72, 73, 75, 77, 78, 79, 81, 82, 84, 85, 86, 87, 90, 92, 94, 95, 96, 97, 98, 99, 101, 102, 103, 105, 106, 107, 108, 109, 113, 114, 115, 118

Offset: 1

Gus Wiseman, Jan 07 2020

nonn

Warning: I have only confirmed the first three terms. The rest are derived from A045779. - Gus Wiseman, Jan 07 2020

R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

Complement of A045779.
The non-strict version is A330976.
Factorizations are A001055, with image A045782, with complement A330976.
Strict factorizations are A045778, with image A045779.
The least positive integer with n strict factorizations is A330974(n).
Cf. A001222, A002033, A025487, A033833, A045780, A045783, A318286, A328966, A330972, A330973, A330997.

nn=20;
fam[n_]:=fam[n]=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[fam[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[Select[fam[#],UnsameQ@@#&]&,2^nn];
Complement[Range[nn],nds]

A330989 Least positive integer with exactly 2^n factorizations into factors > 1, or 0 if no such integer exists.

Original entry on oeis.org

1, 4, 12, 0, 72, 0, 480

Offset: 0

Gus Wiseman, Jan 07 2020

			The A001055(n) factorizations for n = 1, 4, 12, 72:
  ()  (4)    (12)     (72)
      (2*2)  (2*6)    (8*9)
             (3*4)    (2*36)
             (2*2*3)  (3*24)
                      (4*18)
                      (6*12)
                      (2*4*9)
                      (2*6*6)
                      (3*3*8)
                      (3*4*6)
                      (2*2*18)
                      (2*3*12)
                      (2*2*2*9)
                      (2*2*3*6)
                      (2*3*3*4)
                      (2*2*2*3*3)

All nonzero terms belong to A025487 and also A033833.
Factorizations are A001055, with image A045782.
The least number with exactly n factorizations is A330973(n).
Numbers whose number of factorizations is a power of 2 are A330977.
The least number with exactly prime(n) factorizations is A330992(n).
Cf. A002033, A045778, A045783, A318284, A330935, A330972, A330976, A330990, A330991, A331022.

A050322 Number of factorizations indexed by prime signatures: A001055(A025487).

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 7, 5, 7, 9, 12, 11, 11, 16, 19, 21, 15, 29, 26, 30, 15, 31, 38, 22, 47, 52, 45, 36, 57, 64, 30, 77, 98, 67, 74, 97, 66, 105, 42, 109, 118, 92, 109, 171, 97, 141, 162, 137, 165, 56, 212, 181, 52, 198, 189, 289, 139, 250, 257, 269, 254, 77, 382, 267

Offset: 1

Christian G. Bower, Oct 15 1999

nonn

For A025487(m) = 2^k = A000079(k), we have a(m) = A000041(k).

Is a(k) = A000110(k) for A025487(m) = A002110(k)?

			From _Gus Wiseman_, Jan 13 2020: (Start)
The a(1) = 1 through a(11) = 9 factorizations:
  {}  2  4    6    8      12     16       24       30     32         36
         2*2  2*3  2*4    2*6    2*8      3*8      5*6    4*8        4*9
                   2*2*2  3*4    4*4      4*6      2*15   2*16       6*6
                          2*2*3  2*2*4    2*12     3*10   2*2*8      2*18
                                 2*2*2*2  2*2*6    2*3*5  2*4*4      3*12
                                          2*3*4           2*2*2*4    2*2*9
                                          2*2*2*3         2*2*2*2*2  2*3*6
                                                                     3*3*4
                                                                     2*2*3*3
(End)

R. J. Mathar and Michael De Vlieger, Table of n, a(n) for n = 1..5000 (First 300 terms from _R. J. Mathar_)
R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.
Jun Kyo Kim, On highly factorable numbers, Journal Of Number Theory, Vol. 72, No. 1 (1998), pp. 76-91.

Cf. A000041, A000079, A000110, A001055, A002110, A025487.
The version indexed by unsorted prime signature is A331049.
The version indexed by prime shadow (A181819, A181821) is A318284.
This sequence has range A045782 (same as A001055).
Cf. A033833, A045778, A045783, A070175, A181821, A325238, A330972, A330973, A330976, A330989, A330990, A330998, A331050.

A050322 := proc(n)
    A001055(A025487(n)) ;
end proc: # R. J. Mathar, May 25 2017

c[1, r_] := c[1, r] = 1; c[n_, r_] := c[n, r] = Module[{d, i}, d = Select[Divisors[n], 1 < # <= r &]; Sum[c[n/d[[i]], d[[i]]], {i, 1, Length[d]}]]; Map[c[#, #] &, Union@ Table[Times @@ MapIndexed[If[n == 1, 1, Prime[First@ #2]]^#1 &, Sort[FactorInteger[n][[All, -1]], Greater]], {n, Product[Prime@ i, {i, 6}]}]] (* Michael De Vlieger, Jul 10 2017, after Dean Hickerson at A001055 *)
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Length/@facs/@First/@GatherBy[Range[1000],If[#==1,{},Sort[Last/@FactorInteger[#]]]&] (* Gus Wiseman, Jan 13 2020 *)

A330998 Sorted list containing the least number whose inverse prime shadow (A181821) has each possible nonzero number of factorizations into factors > 1.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 10, 12, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 49, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79

Offset: 1

Gus Wiseman, Jan 07 2020

nonn

This is the sorted list of positions of first appearances in A318284 of each element of the range A045782.

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. The inverse prime shadow of n is the least number whose prime exponents are the prime indices of n.

			Factorizations of the inverse prime shadows of the initial terms:
    4    8      12     16       36       24       60       48
    2*2  2*4    2*6    2*8      4*9      3*8      2*30     6*8
         2*2*2  3*4    4*4      6*6      4*6      3*20     2*24
                2*2*3  2*2*4    2*18     2*12     4*15     3*16
                       2*2*2*2  3*12     2*2*6    5*12     4*12
                                2*2*9    2*3*4    6*10     2*3*8
                                2*3*6    2*2*2*3  2*5*6    2*4*6
                                3*3*4             3*4*5    3*4*4
                                2*2*3*3           2*2*15   2*2*12
                                                  2*3*10   2*2*2*6
                                                  2*2*3*5  2*2*3*4
                                                           2*2*2*2*3
The corresponding multiset partitions:
    {11}    {111}      {112}      {1111}        {1122}        {1112}
    {1}{1}  {1}{11}    {1}{12}    {1}{111}      {1}{122}      {1}{112}
            {1}{1}{1}  {2}{11}    {11}{11}      {11}{22}      {11}{12}
                       {1}{1}{2}  {1}{1}{11}    {12}{12}      {2}{111}
                                  {1}{1}{1}{1}  {2}{112}      {1}{1}{12}
                                                {1}{1}{22}    {1}{2}{11}
                                                {1}{2}{12}    {1}{1}{1}{2}
                                                {2}{2}{11}
                                                {1}{1}{2}{2}

Taking n instead of the inverse prime shadow of n gives A330972.
Factorizations are A001055, with image A045782, with complement A330976.
Factorizations of inverse prime shadows are A318284.
Cf. A025487, A033833, A045778, A045783, A181819, A181821, A318286, A325238, A330973, A330989, A330990, A330993, A330997.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
nds=Table[Length[facs[Times@@Prime/@nrmptn[n]]],{n,50}];
Table[Position[nds,i][[1,1]],{i,First/@Gather[nds]}]

A331023 Numerator: factorizations divided by strict factorizations A001055(n)/A045778(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 1, 5, 1, 4, 1, 4, 1, 1, 1, 7, 2, 1, 3, 4, 1, 1, 1, 7, 1, 1, 1, 9, 1, 1, 1, 7, 1, 1, 1, 4, 4, 1, 1, 12, 2, 4, 1, 4, 1, 7, 1, 7, 1, 1, 1, 11, 1, 1, 4, 11, 1, 1, 1, 4, 1, 1, 1, 16, 1, 1, 4, 4, 1, 1, 1, 12, 5, 1, 1, 11, 1, 1, 1, 7, 1, 11, 1, 4, 1, 1, 1, 19, 1, 4, 4, 9, 1, 1, 1, 7, 1

Offset: 1

Gus Wiseman, Jan 08 2020

A factorization of n is a finite, nondecreasing sequence of positive integers > 1 with product n. It is strict if the factors are all different. Factorizations and strict factorizations are counted by A001055 and A045778 respectively.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from exponents in factorization of n

Positions of 1's are A005117.
Positions of 2's appear to be A001248.
The denominators are A331024.
The rounded quotients are A331048.
The same for integer partitions is A330994.
Cf. A001055, A001222, A002033, A045778, A045779, A045780, A045782, A045783, A325755, A326028, A326622, A328966, A330972, A330977, A330991.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[facs[n]]/Length[Select[facs[n],UnsameQ@@#&]],{n,100}]//Numerator

A001055(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1)&&(d<=m), s += A001055(n/d, d))); (s));
A045778(n, m=n) = ((n<=m) + sumdiv(n, d, if((d>1)&&(d<=m)&&(dA045778(n/d, d-1))));
A331023(n) = numerator(A001055(n)/A045778(n)); \\ Antti Karttunen, May 27 2021

a(2^n) = A330994(n).

More terms from Antti Karttunen, May 27 2021

A331024 Denominator: factorizations divided by strict factorizations A001055(n)/A045778(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 3, 1, 3, 1, 1, 1, 5, 1, 1, 2, 3, 1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 1, 5, 1, 1, 1, 3, 3, 1, 1, 7, 1, 3, 1, 3, 1, 5, 1, 5, 1, 1, 1, 9, 1, 1, 3, 4, 1, 1, 1, 3, 1, 1, 1, 9, 1, 1, 3, 3, 1, 1, 1, 7, 2, 1, 1, 9, 1, 1, 1, 5, 1, 9, 1, 3, 1, 1, 1, 10, 1, 3, 3, 5, 1, 1, 1, 5, 1

Offset: 1

Gus Wiseman, Jan 08 2020

A factorization of n is a finite, nondecreasing sequence of positive integers > 1 with product n. It is strict if the factors are all different. Factorizations and strict factorizations are counted by A001055 and A045778 respectively.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from exponents in factorization of n

Positions of 1's include all elements of A001248 as well as A005117. The first position of a 1 that is not in A167207 is 128.
The numerators are A331023.
The rounded quotients are A331048.
The same for integer partitions is A330995.
Cf. A001055, A005117, A045778, A045779, A045780, A045782, A045783, A325755, A326028, A326622, A328966, A330972, A330977, A330991.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[facs[n]]/Length[Select[facs[n],UnsameQ@@#&]],{n,100}]//Denominator

A001055(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1)&&(d<=m), s += A001055(n/d, d))); (s));
A045778(n, m=n) = ((n<=m) + sumdiv(n, d, if((d>1)&&(d<=m)&&(dA045778(n/d, d-1))));
A331024(n) = denominator(A001055(n)/A045778(n)); \\ Antti Karttunen, May 27 2021

a(2^n) = A330995(n).

More terms from Antti Karttunen, May 27 2021

A331050 Positive integers whose number of factorizations into factors > 1 (A001055) is odd.

Original entry on oeis.org

1, 2, 3, 5, 7, 8, 11, 13, 16, 17, 19, 23, 24, 27, 29, 30, 31, 32, 36, 37, 40, 41, 42, 43, 47, 53, 54, 56, 59, 60, 61, 64, 66, 67, 70, 71, 73, 78, 79, 81, 83, 84, 88, 89, 90, 96, 97, 100, 101, 102, 103, 104, 105, 107, 109, 110, 113, 114, 120, 125, 126, 127, 128

Offset: 1

Gus Wiseman, Jan 10 2020

nonn

First differs from A319239 in lacking 256.

Complement of A331051.
The version for powers of two (instead of odds) is A330977.
The version for primes (instead of odds) is A330991.
Cf. A001055, A001221, A001222, A002033, A005117, A045778, A045782, A045783, A330972, A330973.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Select[Range[100],OddQ[Length[facs[#]]]&]

cp's OEIS Frontend

A050345 Number of ways to factor n into distinct factors with one level of parentheses.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A330977 Numbers whose number of factorizations into factors > 1 (A001055) is a power of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A330997 Sorted list containing the least number with each possible nonzero number of factorizations into distinct factors > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A330975 Numbers that are not the number of factorizations of n into distinct factors > 1 for any n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A330989 Least positive integer with exactly 2^n factorizations into factors > 1, or 0 if no such integer exists.

Views

Author

Keywords

Examples

Crossrefs

A050322 Number of factorizations indexed by prime signatures: A001055(A025487).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A330998 Sorted list containing the least number whose inverse prime shadow (A181821) has each possible nonzero number of factorizations into factors > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A331023 Numerator: factorizations divided by strict factorizations A001055(n)/A045778(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A331024 Denominator: factorizations divided by strict factorizations A001055(n)/A045778(n).

Views

Author