Return to Answer

Just thinking about prime denominators: you should be able to take K to be n to the power 3/2, up to some logarithmic stuff. This is just greedily taking a bunch of primes in some interval. There is a little to be gained by using the whole Farey series.

[The condition on the numerators looks slightly troublesome. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). But this can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.]

Just thinking about prime denominators: you should be able to take K to be n to the power 2/3, up to some logarithmic stuff. This is just greedily taking a bunch of primes in some interval. There is a little to be gained by using the whole Farey series.

[The condition on the numerators looks slightly troublesome. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). But this can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.]

Just thinking about prime denominators: you should be able to take K to be n to the power 3/2, up to some logarithmic stuff. This is just greedily taking a bunch of primes in some interval.

[The condition on the numerators looks slightly troublesome. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). But this can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.]

Just thinking about prime denominators: you should be able to take K to be n to the power 3/2, up to some logarithmic stuff. This is just greedily taking a bunch of primes in some interval. There is a little to be gained by using the whole Farey series.

[The condition on the numerators looks slightly troublesome. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). But this can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.]

Distinct fractions with parsimony on denominators looks like the issue of the average order of the Euler totient function $\phi (n)$. Which is well known. Actually here you would get the average order of $n\phi (n)$ coming up, which is not quite so easy to reference, but must be well-known. $\phi (n)$ is typically not much less than n (at worst divide by n to a power like loglog n/log n).

The condition on the numerators looks slightly troublesome, though. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). This can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.

Just thinking about prime denominators: you should be able to take K to be n to the power 3/2, up to some logarithmic stuff. This is just greedily taking a bunch of primes in some interval.

[The condition on the numerators looks slightly troublesome. Just taking the p/q where q is fixed and p coprime to q is going to have the sum of p's around half the sums of q's, on average (or a bit less ...). But this can be worked round: take the "second half" of the p/q with p at least q/2, with the 1 + p/q for the "first half" where p is less than q/2.]