Skip to main content
4 of 7
correct
Charles Matthews
  • 12.6k
  • 35
  • 64

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.

Charles Matthews
  • 12.6k
  • 35
  • 64