A276187 Number of subsets of {1,..,n} of cardinality >= 2 such that the elements of each counted subset are pairwise coprime.

0, 1, 4, 7, 18, 21, 48, 63, 94, 105, 220, 235, 482, 529, 600, 711, 1438, 1501, 3020, 3211, 3594, 3849, 7720, 7975, 11142, 11877, 14628, 15459, 30946, 31201, 62432, 69855, 76126, 80221, 89820, 91611, 183258, 192601, 208600, 214231, 428502, 431573, 863188, 900563

Offset

1,3

Comments

n is prime if and only if a(n) = 2*a(n-1)+n-1. - Robert Israel, Aug 24 2016

Links

Robert Israel, Table of n, a(n) for n = 1..340

Formula

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

Example

From Gus Wiseman, May 08 2021: (Start)
The a(2) = 1 through a(6) = 21 sets:
  {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)

Maple

f:= proc(S) option remember;
    local s, Sp;
    if S = {} then return 1 fi;
    s:= S[-1];
    Sp:= S[1..-2];
    procname(Sp) + procname(select(t -> igcd(t, s)=1, Sp))
end proc:
seq(f({$1..n}) - n - 1, n=1..50); # Robert Israel, Aug 24 2016

Mathematica

f[S_] := f[S] = Module[{s, Sp}, If[S == {}, Return[1]]; s = S[[-1]]; Sp = S[[1;; -2]]; f[Sp] + f[Select[Sp, GCD[#, s] == 1&]]];
Table[f[Range[n]] - n - 1, {n, 1, 50}] (* Jean-François Alcover, Sep 15 2022, after Robert Israel *)

Prog

(Sage)
from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
def is_coprime(x, y): return gcd(x, y) == 1
max_n = 40
seq = []
for n in range(1, max_n+1):
    P = PairwiseCompatibleSubsets(range(1, n+1), is_coprime)
    a_n = len([1 for s in P.list() if len(s) > 1])
    seq.append(a_n)
print(seq)
(PARI) f(n, k=1)=if(n==1, return(2)); if(gcd(k, n)==1, f(n-1, n*k)) + f(n-1, k)
a(n)=f(n)-n-1 \\ Charles R Greathouse IV, Aug 24 2016

Crossrefs

Cf. A000010, A002088, A018805.

The case of pairs is A015614.

The indivisible instead of coprime version is A051026(n) - n.

Allowing empty sets and singletons gives A084422.

The relatively prime instead of pairwise coprime version is A085945(n) - 1.

Allowing all singletons gives A187106.

Allowing only the singleton {1} gives A320426.

Row sums of A320436, each minus one.

The maximal case is counted by A343659.

The version for sets of divisors is A343655(n) - 1.

A000005 counts divisors.

A186972 counts pairwise coprime k-sets containing n.

A186974 counts pairwise coprime k-sets.

A326675 ranks pairwise coprime non-singleton sets.

Cf. A007360, A063647, A186971, A302696, A305713, A320423, A320430, A326077, A327516, A337485.

Sequence in context: A077274 A292850 A080650 * A357041 A318025 A005509

Adjacent sequences: A276184 A276185 A276186 * A276188 A276189 A276190

Keyword

nonn

Author

Robert C. Lyons, Aug 23 2016

Extensions

Name and example edited by Robert Israel, Aug 24 2016

Status

approved