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

0, 1, 2, 4, 10, 20, 44, 88, 204, 440, 908, 1816, 3776, 7552, 15364, 31240, 63744, 127488, 257592, 515184, 1036336, 2079312, 4166408, 8332816, 16709632, 33470464, 66978208, 134067488, 268236928, 536473856, 1073233840, 2146467680, 4293851680, 8588355424, 17177430640

Offset

0,3

Links

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

Formula

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

Example

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

Mathematica

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

Crossrefs

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

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

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

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

For non-isomorphic multiset partitions we have A368097, complement A368098.

The version for factorizations is A368413, complement A368414.

The complement is counted by A370582.

For a unique choice we have A370584.

Partial sums of A370587, complement A370586.

The minimal case is A370591.

The version for partitions is A370593, complement A370592.

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

A006530 gives greatest prime factor, least A020639.

A027746 lists prime factors, A112798 indices, length A001222.

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

Cf. A000040, A000720, A001055, A001414, A003963, A005117, A045778, A355739, A355745, A367867, A367905, A368187.

Sequence in context: A094536 A323445 A307768 * A297183 A232466 A003407

Adjacent sequences: A370580 A370581 A370582 * A370584 A370585 A370586

Keyword

nonn

Author

Gus Wiseman, Feb 26 2024

Extensions

a(19)-a(34) from Alois P. Heinz, Feb 27 2024

Status

approved