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

Author

Gus Wiseman, Feb 25 2024

Keywords

• nonn

Examples

			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}
		

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.

Programs

Mathematica

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

Formula

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

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

Extensions

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

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