A370582 Number of subsets of {1..n} such that it is possible to choose a different prime factor of each element.

1, 1, 2, 4, 6, 12, 20, 40, 52, 72, 116, 232, 320, 640, 1020, 1528, 1792, 3584, 4552, 9104, 12240, 17840, 27896, 55792, 67584, 83968, 130656, 150240, 198528, 397056, 507984, 1015968, 1115616, 1579168, 2438544, 3259680, 3730368, 7460736, 11494656, 16145952, 19078464, 38156928

Offset

0,3

Links

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

Formula

a(p) = 2 * a(p-1) for prime p. - David A. Corneth, Feb 25 2024

a(n) = 2^n - A370583(n).

Example

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

Mathematica

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

Crossrefs

The version for set-systems is A367902, ranks A367906, unlabeled A368095.

The complement for set-systems is A367903, ranks A367907, unlabeled A368094.

For unlabeled multiset partitions we have A368098, complement A368097.

Multisets of this type are ranked by A368100, complement A355529.

For divisors instead of factors we have A368110, complement A355740.

The version for factorizations is A368414, complement A368413.

The complement is counted by A370583.

For a unique choice we have A370584.

The maximal case is A370585.

Partial sums of A370586, complement A370587.

The version for partitions is A370592, complement A370593.

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

A006530 gives greatest prime factor, least A020639.

A027746 lists prime factors, A112798 indices, length A001222.

A307984 counts Q-bases of logarithms of positive integers.

A355741 counts choices of a prime factor of each prime index.

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

Sequence in context: A078025 A178901 A164146 * A279245 A090906 A047141

Adjacent sequences: A370579 A370580 A370581 * A370583 A370584 A370585

Keyword

nonn

Author

Gus Wiseman, Feb 25 2024

Extensions

a(19) from David A. Corneth, Feb 25 2024

a(20)-a(41) from Alois P. Heinz, Feb 25 2024

Status

approved