login
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.
15

%I #24 May 10 2021 23:30:34

%S 1,2,5,8,19,22,49,64,95,106,221,236,483,530,601,712,1439,1502,3021,

%T 3212,3595,3850,7721,7976,11143,11878,14629,15460,30947,31202,62433,

%U 69856,76127,80222,89821,91612,183259,192602,208601,214232,428503,431574,863189

%N 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.

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

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

%F a(n) = A276187(n) + 1. - _Gus Wiseman_, May 08 2021

%e 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

%e From _Gus Wiseman_, May 09 2021: (Start)

%e The a(2) = 2 through a(6) = 22 sets:

%e {1} {1} {1} {1} {1}

%e {1,2} {1,2} {1,2} {1,2} {1,2}

%e {1,3} {1,3} {1,3} {1,3}

%e {2,3} {1,4} {1,4} {1,4}

%e {1,2,3} {2,3} {1,5} {1,5}

%e {3,4} {2,3} {1,6}

%e {1,2,3} {2,5} {2,3}

%e {1,3,4} {3,4} {2,5}

%e {3,5} {3,4}

%e {4,5} {3,5}

%e {1,2,3} {4,5}

%e {1,2,5} {5,6}

%e {1,3,4} {1,2,3}

%e {1,3,5} {1,2,5}

%e {1,4,5} {1,3,4}

%e {2,3,5} {1,3,5}

%e {3,4,5} {1,4,5}

%e {1,2,3,5} {1,5,6}

%e {1,3,4,5} {2,3,5}

%e {3,4,5}

%e {1,2,3,5}

%e {1,3,4,5}

%e (End)

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

%Y The case of pairs is A015614.

%Y The case with singletons is A187106.

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

%Y Row sums of A320436.

%Y The version for divisors > 1 is A343654.

%Y The version for divisors without singletons is A343655.

%Y The maximal version is A343659.

%Y A018892 counts coprime unordered pairs of divisors.

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

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

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

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

%K nonn

%O 1,2

%A _Gus Wiseman_, Jan 08 2019

%E a(25)-a(43) from _Alois P. Heinz_, Jan 08 2019