login
A186971
Maximal cardinality of a subset of {1, 2, ..., n} containing n and having pairwise coprime elements.
7
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, 12, 11, 11, 11, 11, 13, 12, 12, 12, 14, 12, 15, 14, 14, 14, 16, 15, 16, 15, 15, 15, 17, 16, 16, 16, 16, 16, 18, 16, 19, 18, 18, 19, 18, 17, 20
OFFSET
1,2
COMMENTS
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).
Max { a(i) : i=1..n } = A036234(n).
LINKS
FORMULA
a(n) = n if n<4, a(n) = A000720(n) - A001221(n) + 2 else.
EXAMPLE
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.
a(9) = 5, the maximal subsets are {1,2,5,7,9}, {1,4,5,7,9}, {1,5,7,8,9}.
MAPLE
with(numtheory):
a:= n-> `if`(n<4, n, pi(n) -nops(factorset(n)) +2):
seq(a(n), n=1..120);
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 01 2011
STATUS
approved