A343659 Number of maximal pairwise coprime subsets of {1..n}.

1, 1, 1, 2, 2, 3, 3, 4, 7, 9, 9, 10, 10, 12, 16, 19, 19, 20, 20, 22, 28, 32, 32, 33, 54, 61, 77, 84, 84, 85, 85, 94, 112, 123, 158, 161, 161, 176, 206, 212, 212, 214, 214, 229, 241, 260, 260, 263, 417, 428, 490, 521, 521, 526, 655, 674, 764, 818, 818, 820, 820, 874, 918, 975, 1182, 1189, 1189

Offset

1,4

Comments

For this sequence, it does not matter whether singletons are considered pairwise coprime.

For n > 2, also the number of maximal pairwise coprime subsets of {2..n}.

For each prime p <= n, p divides exactly one element of each maximal subset. - Bert Dobbelaere, May 04 2021

Links

Bert Dobbelaere, Table of n, a(n) for n = 1..500

Bert Dobbelaere, Python program

Example

The a(1) = 1 through a(9) = 7 subsets:
  {1}  {12}  {123}  {123}  {1235}  {156}   {1567}   {1567}   {1567}
                    {134}  {1345}  {1235}  {12357}  {12357}  {12357}
                                   {1345}  {13457}  {13457}  {12579}
                                                    {13578}  {13457}
                                                             {13578}
                                                             {14579}
                                                             {15789}

Mathematica

fasmax[y_]:=Complement[y, Union@@Most@*Subsets/@y];
Table[Length[fasmax[Select[Subsets[Range[n]], CoprimeQ@@#&]]], {n, 15}]

Crossrefs

The case of pairs is A015614.

The case of triples is A015617.

The non-maximal version counting empty sets and singletons is A084422.

The non-maximal version counting singletons is A187106.

The non-maximal version is A320426(n) = A276187(n) + 1.

The version for indivisibility instead of coprimality is A326077.

The version for sets of divisors is A343652.

The version for sets of divisors > 1 is A343660.

A018892 counts coprime unordered pairs of divisors.

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

A100565 counts pairwise coprime unordered triples of divisors.

Cf. A007360, A067824, A087087, A225520, A324837, A325683, A325859, A326358, A326496, A326675, A333227, A343653, A343655.

Sequence in context: A067619 A236972 A184351 * A146922 A283363 A236210

Adjacent sequences: A343656 A343657 A343658 * A343660 A343661 A343662

Keyword

nonn

Author

Gus Wiseman, Apr 26 2021

Extensions

More terms from Bert Dobbelaere, May 04 2021

Status

approved