

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Alois P. Heinz, Table of n, a(n) for n = 1..10000


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

Cf. A001221, A000720, A186994, A036234.
Sequence in context: A038203 A255239 A316339 * A329255 A262535 A096827
Adjacent sequences: A186968 A186969 A186970 * A186972 A186973 A186974


KEYWORD

nonn


AUTHOR

Alois P. Heinz, Mar 01 2011


STATUS

approved



