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

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

Author

Alois P. Heinz, Mar 01 2011

Keywords

• nonn

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).

Examples

			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}.
		

Links

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

Crossrefs

Cf. A001221, A000720, A186994, A036234.

Programs

Maple

with(numtheory):
a:= n-> `if`(n<4, n, pi(n) -nops(factorset(n)) +2):
seq(a(n), n=1..120);

Formula

a(n) = n if n<4, a(n) = A000720(n) - A001221(n) + 2 else.