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 .
Charles Matthews
- 12.6k
- 35
- 64