Math Tutoring Service

See my Mathematics Tutoring Service on Thumbtack

A simple (?) number theory conjecture

Call a set S of positive integers non-divisible if, whenever a and b belong to S, it is not true that (a|b or b|a). For example, the set of prime numbers is non-divisible. Let S(n) be the set of the first n positive integers, and let f(n) be the cardinality of the largest non-divisible subset of S(n). Then clearly f(n) >= pi(n), where pi(n) denotes the number of prime numbers <= n. Furthermore, I know a pretty proof (published, but not by me) that shows f(n) <= n/2 (n even). That is, in any subset of n/2 + 1 positive integers all <= n, at least one integer divides another integer in the set. This proof involves the pigeonhole principle. So, pi(n) <= f(n) <= n/2. (n even) My conjecture is that, in fact, f(n) = pi(n) for all n > 1. Does anyone have a counterexample or a proof? It seems like it should be very simple.

1 comment:

SR lakshmi said...

 Interactive online math homework help ,Best site for   math homework help solutions