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

1, 1, 2, 4, 6, 12, 18, 36, 48, 68, 104, 208, 284, 568, 888, 1296, 1548, 3096, 3968

Offset

0,3

Comments

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

Links

Table of n, a(n) for n=0..18.

Example

The a(0) = 1 through a(6) = 18 subsets:
  {}  {}  {}   {}     {}     {}       {}
          {2}  {2}    {2}    {2}      {2}
               {3}    {3}    {3}      {3}
               {2,3}  {4}    {4}      {4}
                      {2,3}  {5}      {5}
                      {3,4}  {2,3}    {2,3}
                             {2,5}    {2,5}
                             {3,4}    {2,6}
                             {3,5}    {3,4}
                             {4,5}    {3,5}
                             {2,3,5}  {3,6}
                             {3,4,5}  {4,5}
                                      {4,6}
                                      {2,3,5}
                                      {2,5,6}
                                      {3,4,5}
                                      {3,5,6}
                                      {4,5,6}

Mathematica

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

Crossrefs

For divisors instead of factors we have A051026, cf. A368110, A355740.

The version for set-systems is A367904, ranks A367908.

Multisets of this type are ranked by A368101, cf. A368100, A355529.

For existence we have A370582, differences A370586.

For nonexistence we have A370583, differences A370587.

Maximal sets of this type are counted by A370585.

The version for partitions is A370594, cf. A370592, A370593.

For binary indices instead of factors we have A370638, cf. A370636, A370637.

The version for factorizations is A370645, cf. A368414, A368413.

For unlabeled multiset partitions we have A370646, cf. A368098, A368097.

A006530 gives greatest prime factor, least A020639.

A027746 lists prime factors, A112798 indices, length A001222.

A355741 counts ways to choose a prime factor of each prime index.

Cf. A000040, A000720, A003963, A005117, A045778, A133686, A307984, A355739, A355744, A355745, A367905.

Sequence in context: A063516 A306315 A104352 * A133488 A351016 A068911

Adjacent sequences: A370581 A370582 A370583 * A370585 A370586 A370587

Keyword

nonn,more

Author

Gus Wiseman, Feb 26 2024

Status

approved