A370585 -id:A370585 - cp's OEIS frontend

A370817 Greatest number of multisets that can be obtained by choosing a prime factor of each factor in an integer factorization of n into unordered factors > 1.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 2, 2, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 4, 1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 4, 2, 2, 2

Offset: 1

Gus Wiseman, Mar 07 2024

nonn

First differs from A096825 at a(210) = 4, A096825(210) = 6.
First differs from A343943 at a(210) = 4, A343943(210) = 6.
First differs from A345926 at a(90) = 4, A345926(90) = 3.

			For the factorizations of 60 we have the following choices (using prime indices {1,2,3} instead of prime factors {2,3,5}):
  (2*2*3*5): {{1,1,2,3}}
   (2*2*15): {{1,1,2},{1,1,3}}
   (2*3*10): {{1,1,2},{1,2,3}}
    (2*5*6): {{1,1,3},{1,2,3}}
    (3*4*5): {{1,2,3}}
     (2*30): {{1,1},{1,2},{1,3}}
     (3*20): {{1,2},{2,3}}
     (4*15): {{1,2},{1,3}}
     (5*12): {{1,3},{2,3}}
     (6*10): {{1,1},{1,2},{1,3},{2,3}}
       (60): {{1},{2},{3}}
So a(60) = 4.

Max Alekseyev, Table of n, a(n) for n = 1..10000

For all divisors (not just prime factors) we have A370816.
The version for partitions is A370809, for all divisors A370808.
A000005 counts divisors.
A001055 counts factorizations, strict A045778.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A355741 chooses prime factors of prime indices, variations A355744, A355745.
A368413 counts non-choosable factorizations, complement A368414.
A370813 counts non-divisor-choosable factorizations, complement A370814.
Cf. A000792, A048249, A066739, A319055, A319057, A355529, A355535, A367771, A368100, A370585.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Max[Length[Union[Sort/@Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#]]]&/@facs[n]],{n,100}]

A387113 Numbers whose prime indices do not have (strictly) choosable initial intervals.

Original entry on oeis.org

4, 8, 12, 16, 18, 20, 24, 27, 28, 32, 36, 40, 44, 48, 52, 54, 56, 60, 64, 68, 72, 76, 80, 81, 84, 88, 90, 92, 96, 100, 104, 108, 112, 116, 120, 124, 126, 128, 132, 135, 136, 140, 144, 148, 150, 152, 156, 160, 162, 164, 168, 172, 176, 180, 184, 188, 189, 192

Offset: 1

Gus Wiseman, Aug 24 2025

The initial interval of a nonnegative integer x is the set {1,...,x}.
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.
We say that a set or sequence of nonempty sets is choosable iff it is possible to choose a different element from each set. For example, ({1,2},{1},{1,3}) is choosable because we have the choice (2,1,3), but ({1,2,3},{1},{1,3},{2}) is not.
This sequence lists all numbers k such that if the prime indices of k are (x1,x2,...,xz), then the sequence of sets (initial intervals) ({1,...,x1},{1,...,x2},...,{1,...,xz}) is not choosable.

			The prime indices of 18 are {1,2,2}, with initial intervals ({1},{1,2},{1,2}), which have choices (1,1,1), (1,1,2), (1,2,1), (1,2,2), and since none of these are strict, 18 is in the sequence.
The prime indices of 85 are {3,7}, with initial intervals {{1,2,3},{1,2,3,4,5,6,7}}, which are choosable, so 85 is in not the sequence.
The prime indices of 90 are {1,2,2,3}, with initial intervals {{1},{1,2},{1,2},{1,2,3}}, which are not choosable, so 90 is in the sequence.
The terms together with their prime indices begin:
    4: {1,1}
    8: {1,1,1}
   12: {1,1,2}
   16: {1,1,1,1}
   18: {1,2,2}
   20: {1,1,3}
   24: {1,1,1,2}
   27: {2,2,2}
   28: {1,1,4}
   32: {1,1,1,1,1}
   36: {1,1,2,2}
   40: {1,1,1,3}
   44: {1,1,5}
   48: {1,1,1,1,2}
   52: {1,1,6}
   54: {1,2,2,2}
   56: {1,1,1,4}
   60: {1,1,2,3}
   64: {1,1,1,1,1,1}

For partitions instead of initial intervals we have A276079, complement A276078.
For prime factors instead of initial intervals we have A355529, complement A368100.
For divisors instead of initial intervals we have A355740, complement A368110.
These are the positions of 0 in A387111, complement A387134.
The complement is A387112.
Partitions of this type are counted by A387118, complement A238873.
For strict partitions instead of initial intervals we have A387137, complement A387176.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, row sums A056239 or A066328, lengths A001222.
A120383 lists numbers divisible by all of their prime indices.
A367902 counts choosable set-systems, complement A367903.
A370582 counts sets with choosable prime factors, complement A370583.
A370585 counts maximal subsets with choosable prime factors.
Cf. A003963, A005703, A052335, A239312, A335433, A335448, A355739, A355747, A370592, A383706, A387110.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Select[Tuples[Range/@prix[#]],UnsameQ@@#&]=={}&]

A370588 Number of subsets of {1..n} containing n such that only one set can be obtained by choosing a different prime factor of each element.

Original entry on oeis.org

0, 0, 1, 2, 2, 6, 6, 18, 12, 20, 36, 104, 76, 284, 320, 408, 252, 1548, 872, 3968, 2800, 4704, 8568, 24008, 10832, 14832, 40688, 18240, 43632, 176240, 97344, 449824, 95328, 404992, 760752, 698864, 436464, 3296048, 3564576, 4057904, 2677776, 16892352, 8676576

Offset: 0

Gus Wiseman, Feb 28 2024

nonn

For example, the only choice of a different prime factor of each element of (4,5,6) is (2,5,3), so {4,5,6} is counted under a(6).

			The a(0) = 0 through a(8) = 12 subsets:
  .  .  {2}  {3}    {4}    {5}      {2,6}    {7}        {8}
             {2,3}  {3,4}  {2,5}    {3,6}    {2,7}      {3,8}
                           {3,5}    {4,6}    {3,7}      {5,8}
                           {4,5}    {2,5,6}  {4,7}      {6,8}
                           {2,3,5}  {3,5,6}  {5,7}      {7,8}
                           {3,4,5}  {4,5,6}  {2,3,7}    {3,5,8}
                                             {2,5,7}    {3,7,8}
                                             {2,6,7}    {5,6,8}
                                             {3,4,7}    {5,7,8}
                                             {3,5,7}    {6,7,8}
                                             {3,6,7}    {3,5,7,8}
                                             {4,5,7}    {5,6,7,8}
                                             {4,6,7}
                                             {2,3,5,7}
                                             {2,5,6,7}
                                             {3,4,5,7}
                                             {3,5,6,7}
                                             {4,5,6,7}

First differences of A370584, cf. A370582, complement A370583.
For any number of choices we have A370586, complement A370587.
For binary indices see A370638, A370639, complement A370589.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, indices A112798, length A001222.
A355741 counts choices of a prime factor of each prime index.
A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.
A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.
A368098 counts choosable unlabeled multiset partitions, complement A368097.
A368100 ranks choosable multisets, complement A355529.
A368414 counts choosable factorizations, complement A368413.
A370585 counts maximal choosable sets.
A370592 counts choosable partitions, complement A370593.
A370636 counts choosable subsets for binary indices, complement A370637.
Cf. A000040, A000720, A005117, A045778, A133686, A355739, A355744, A355745, A367771, A367905.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n] && Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==1&]],{n,0,10}]

More terms from Jinyuan Wang, Mar 28 2025

A370590 Number of maximal subsets of {1..n} containing n such that it is possible to choose a different prime factor of each element (choosable).

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 3, 5, 2, 4, 14, 25, 13, 38, 46, 66, 28, 178, 57, 235, 106, 238, 656, 1235, 288, 445, 2192, 664, 2016, 6840, 2300, 9140, 888, 6236, 17692, 14724, 7320, 56000, 60472, 70252, 37160, 223884, 66428, 290312, 113172, 80544, 517392, 1001420, 114336

Offset: 0

Gus Wiseman, Feb 28 2024

nonn

For example, the set {4,7,9,10} has choice (2,7,3,5) so is counted under a(10).

			The a(0) = 0 through a(10) = 14 subsets (A = 10):
  .  .  2  23  34  235  256  2357  3578  2579  237A
                   345  356  2567  5678  4579  267A
                        456  3457        5679  279A
                             3567        5789  347A
                             4567              357A
                                               367A
                                               378A
                                               467A
                                               479A
                                               567A
                                               579A
                                               678A
                                               679A
                                               789A

Not requiring n gives A370585, maximal case of A370582, complement A370583.
Maximal case of A370586, complement A370587, unique A370588.
An opposite version is A370591.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, indices A112798, length A001222.
A355741 counts choices of a prime factor of each prime index.
A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.
A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.
A368098 counts choosable unlabeled multiset partitions, complement A368097.
A368100 ranks choosable multisets, complement A355529.
A368414 counts choosable factorizations, complement A368413.
A370592 counts choosable partitions, complement A370593.
Cf. A000040, A000720, A133686, A355739, A355744, A355745, A367771, A370584, A370636, A370639.

Table[Length[Select[Subsets[Range[n],{PrimePi[n]}],MemberQ[#,n]&&Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#],UnsameQ@@#&]]>0&]],{n,0,10}]

More terms from Jinyuan Wang, Feb 14 2025

A370646 Number of non-isomorphic multiset partitions of weight n such that only one set can be obtained by choosing a different element of each block.

Original entry on oeis.org

1, 1, 2, 4, 10, 23, 62, 165, 475, 1400, 4334

Offset: 0

Gus Wiseman, Mar 12 2024

A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition is the sum of cardinalities of its elements.

			The multiset partition {{3},{1,3},{2,3}} has unique choice (3,1,2) so is counted under a(5).
Representatives of the a(1) = 1 through a(5) = 23 multiset partitions:
  {1}  {11}    {111}      {1111}        {11111}
       {1}{2}  {1}{22}    {1}{122}      {11}{122}
               {2}{12}    {11}{22}      {1}{1222}
               {1}{2}{3}  {12}{12}      {11}{222}
                          {1}{222}      {12}{122}
                          {12}{22}      {1}{2222}
                          {2}{122}      {12}{222}
                          {1}{2}{33}    {2}{1122}
                          {1}{3}{23}    {2}{1222}
                          {1}{2}{3}{4}  {22}{122}
                                        {1}{2}{233}
                                        {1}{22}{33}
                                        {1}{23}{23}
                                        {1}{2}{333}
                                        {1}{23}{33}
                                        {1}{3}{233}
                                        {2}{12}{33}
                                        {2}{13}{23}
                                        {2}{3}{123}
                                        {3}{13}{23}
                                        {1}{2}{3}{44}
                                        {1}{2}{4}{34}
                                        {1}{2}{3}{4}{5}

For existence we have A368098, complement A368097.
Multisets of this type are ranked by A368101, see also A368100, A355529.
Subsets of this type are counted by A370584, see also A370582, A370583.
Maximal sets of this type are counted by A370585.
Partitions of this type are counted by A370594, see also A370592, A370593.
Subsets of this type are also counted by A370638, see also A370636, A370637.
Factorizations of this type are A370645, see also A368414, A368413.
Set-systems of this type are A370818, see also A367902, A367903.
A000110 counts set partitions, non-isomorphic A000041.
A001055 counts factorizations, strict A045778.
A007716 counts non-isomorphic multiset partitions, connected A007718.
Cf. A000612, A055621, A283877, A300913, A302545, A316983, A319616, A330223, A368095, A368412, A368422.

A387328 Number of integer partitions of n whose parts have choosable sets of integer partitions.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 5, 7, 10, 13, 17, 22, 28, 36, 46, 58, 73, 91, 114, 141, 174, 214, 262, 320, 389, 472, 571, 688, 828, 993, 1189, 1419, 1690, 2009, 2383, 2821, 3334, 3931, 4628, 5439, 6381, 7474, 8741, 10207, 11902, 13858, 16114, 18710, 21698, 25130, 29070

Offset: 0

Gus Wiseman, Sep 01 2025

First differs from A052335 at A052335(20) = 173, a(20) = 174, corresponding to the partition (4,4,4,4,4).
a(n) is the number of integer partitions of n such that it is possible to choose a sequence of distinct integer partitions, one of each part.
Also the number of integer partitions y of n with no part k whose multiplicity in y exceeds A000041(k).

			The a(1) = 1 through a(9) = 13 partitions:
  (1)  (2)  (3)   (4)   (5)    (6)    (7)    (8)     (9)
            (21)  (22)  (32)   (33)   (43)   (44)    (54)
                  (31)  (41)   (42)   (52)   (53)    (63)
                        (221)  (51)   (61)   (62)    (72)
                               (321)  (322)  (71)    (81)
                                      (331)  (332)   (333)
                                      (421)  (422)   (432)
                                             (431)   (441)
                                             (521)   (522)
                                             (3221)  (531)
                                                     (621)
                                                     (3321)
                                                     (4221)

The strict case is A000009.
For initial intervals instead of partitions we have A238873, complement A387118.
For divisors instead of partitions we have A239312, complement A370320.
For prime factors instead of partitions we have A370592, ranks A368100.
The complement for prime factors is A370593, ranks A355529.
The complement is counted by A387134, ranks A387577.
For sets of strict partitions we have A387178, complement A387137.
These partitions are ranked by A387576.
A000005 counts divisors.
A000041 counts integer partitions.
Cf. A052335, A052337, A335433, A367771, A370585, A370804.

Table[Length[Select[IntegerPartitions[n],Select[Tuples[IntegerPartitions/@#],UnsameQ@@#&]!={}&]],{n,0,15}]

cp's OEIS Frontend

A370817 Greatest number of multisets that can be obtained by choosing a prime factor of each factor in an integer factorization of n into unordered factors > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A387113 Numbers whose prime indices do not have (strictly) choosable initial intervals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A370588 Number of subsets of {1..n} containing n such that only one set can be obtained by choosing a different prime factor of each element.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A370590 Number of maximal subsets of {1..n} containing n such that it is possible to choose a different prime factor of each element (choosable).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A370646 Number of non-isomorphic multiset partitions of weight n such that only one set can be obtained by choosing a different element of each block.

Views

Author

Keywords

Comments

Examples

Crossrefs

A387328 Number of integer partitions of n whose parts have choosable sets of integer partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica