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, in that it means the exponent of n you need is easily at most $1 +\epsilon$, and in fact the real average order is more like n/loglog n .