A320426 Number of nonempty pairwise coprime subsets of {1,...,n}, where a single number is not considered to be pairwise coprime unless it is equal to 1.

1, 2, 5, 8, 19, 22, 49, 64, 95, 106, 221, 236, 483, 530, 601, 712, 1439, 1502, 3021, 3212, 3595, 3850, 7721, 7976, 11143, 11878, 14629, 15460, 30947, 31202, 62433, 69856, 76127, 80222, 89821, 91612, 183259, 192602, 208601, 214232, 428503, 431574, 863189

Offset

1,2

Comments

Two or more numbers are pairwise coprime if no pair of them has a common divisor > 1.

Links

Table of n, a(n) for n=1..43.

Formula

a(n) = A187106(n) - n + 1 = A084422(n) - n.

a(n) = A276187(n) + 1. - Gus Wiseman, May 08 2021

Example

The a(4) = 8 subsets of {1,2,3,4} are {1}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}. - Michael B. Porter, Jan 12 2019
From Gus Wiseman, May 09 2021: (Start)
The a(2) = 2 through a(6) = 22 sets:
   {1}     {1}      {1}       {1}        {1}
  {1,2}   {1,2}    {1,2}     {1,2}      {1,2}
          {1,3}    {1,3}     {1,3}      {1,3}
          {2,3}    {1,4}     {1,4}      {1,4}
         {1,2,3}   {2,3}     {1,5}      {1,5}
                   {3,4}     {2,3}      {1,6}
                  {1,2,3}    {2,5}      {2,3}
                  {1,3,4}    {3,4}      {2,5}
                             {3,5}      {3,4}
                             {4,5}      {3,5}
                            {1,2,3}     {4,5}
                            {1,2,5}     {5,6}
                            {1,3,4}    {1,2,3}
                            {1,3,5}    {1,2,5}
                            {1,4,5}    {1,3,4}
                            {2,3,5}    {1,3,5}
                            {3,4,5}    {1,4,5}
                           {1,2,3,5}   {1,5,6}
                           {1,3,4,5}   {2,3,5}
                                       {3,4,5}
                                      {1,2,3,5}
                                      {1,3,4,5}
(End)

Mathematica

Table[Length[Select[Subsets[Range[n]], CoprimeQ@@#&]], {n, 10}]

Crossrefs

The case of pairs is A015614.

The case with singletons is A187106.

The version without singletons (except {1}) is A276187.

Row sums of A320436.

The version for divisors > 1 is A343654.

The version for divisors without singletons is A343655.

The maximal version is A343659.

A018892 counts coprime unordered pairs of divisors.

A051026 counts pairwise indivisible subsets of {1...n}.

A087087 ranks pairwise coprime subsets of {1...n}.

A326675 ranks pairwise coprime non-singleton subsets of {1...n}.

Cf. A007359, A007360, A066620, A089233, A100565, A225520, A325683, A326359, A337485, A343652.

Sequence in context: A197211 A256723 A032063 * A133147 A358828 A082630

Adjacent sequences: A320423 A320424 A320425 * A320427 A320428 A320429

Keyword

nonn

Author

Gus Wiseman, Jan 08 2019

Extensions

a(25)-a(43) from Alois P. Heinz, Jan 08 2019

Status

approved