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

Author

Gus Wiseman, Jan 08 2019

Keywords

• nonn

Comments

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

Examples

			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)
		

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.

Programs

Mathematica

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

Formula

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

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

Extensions

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