login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 29 10:30 EDT 2022. Contains 357088 sequences. (Running on oeis4.)