Let be a set of positive integers satisfying the following two conditions: - For each positive integer , at least one of is in . - If are positive integers such that and , then Suppose that has natural density . Compute the minimum possible value of . Note: has natural density if approaches as approaches .
Solution
The optimal value of is . This is attained by letting be the set of integers for which and . Let be a set of positive integers satisfying the two conditions. For each prime , let : . We claim that in fact is precisely the set of positive integers for which for each prime . Let be prime and suppose that , with . Then, setting and in the second condition gives that as well. So, if we have an integer for which for each prime , we can start with any element of and apply this step for each prime divisor of and to obtain . Now we deal with the first condition. Let be any positive integer. We will compute the least positive integer such that . By the above result, we can work with each prime separately. For a given prime , let be the least element of with . Then we must have , and equality for all primes is sufficient. So, if the elements of are , then is the worst case value for . We conclude two things from this. First, we must have by condition 1, and in fact this is sufficient. Second, since we only care about and would like to minimize , the optimal choice for is an arithmetic progression with first term and common difference . So we assume that each is of this form. Let . We now compute . Note that is the set of integers such that for each prime , for some positive integers with . This means that each prime contributes a factor of to the density of . Multiplying over all primes gives , where is the sum of divisors of . So, it suffices to maximize for . By inspection, is optimal, giving .