cp's OEIS Frontend

A186971 Maximal cardinality of a subset of {1, 2, ..., n} containing n and having pairwise coprime elements.

%I A186971 #15 Mar 12 2015 04:48:51
%S A186971 1,2,3,3,4,3,5,5,5,4,6,5,7,6,6,7,8,7,9,8,8,8,10,9,10,9,10,9,11,9,12,
%T A186971 12,11,11,11,11,13,12,12,12,14,12,15,14,14,14,16,15,16,15,15,15,17,16,
%U A186971 16,16,16,16,18,16,19,18,18,19,18,17,20
%N A186971 Maximal cardinality of a subset of {1, 2, ..., n} containing n and having pairwise coprime elements.
%C A186971 In general there exist different maximal subsets for a given n.  One of these is S = {1, n} union ({primes <= n} \ {prime factors of n}).  The number of different subsets is A186994(n).
%C A186971 Max { a(i) : i=1..n } = A036234(n).
%H A186971 Alois P. Heinz, <a href="/A186971/b186971.txt">Table of n, a(n) for n = 1..10000</a>
%F A186971 a(n) = n if n<4, a(n) = A000720(n) - A001221(n) + 2 else.
%e A186971 a(4) = 3 because 4 and 2 are not coprime and {1,3,4} is a maximal subset of {1,2,3,4} with pairwise coprime elements.
%e A186971 a(9) = 5, the maximal subsets are {1,2,5,7,9}, {1,4,5,7,9}, {1,5,7,8,9}.
%p A186971 with(numtheory):
%p A186971 a:= n-> `if`(n<4, n, pi(n) -nops(factorset(n)) +2):
%p A186971 seq(a(n), n=1..120);
%Y A186971 Cf. A001221, A000720, A186994, A036234.
%K A186971 nonn
%O A186971 1,2
%A A186971 _Alois P. Heinz_, Mar 01 2011