Number of rationals with denominator less than $N$

135 Views Asked by At

This is probably a duplicate since it seems like elementary number theory, but didn't find it after a cursory search. Let $r(N)$ be the number of rationals in $[0,1]$ with denominator less than or equal to $N$. Is there an asymptotic expression for $r(N)$?

A cute Mathematica script shows the following:

r[m_] := Union[Flatten@Table[k/j, {j, m}, {k, 0, j}]];
ListLinePlot[Table[Length[r[k]]/k^2, {k, 150}], PlotRange -> {0, 0.5}]

enter image description here

and Length[r[2000]]/2000.0^2 gives 0.304147. If $r(N)$ has a quadratic asymptotic expression, what is its coefficient?

1

There are 1 best solutions below

0
On

As Janko pointed out, we have $$r(N)=\sum_{n=-1}^N\varphi(n)\sim\frac{3}{\pi^2}N^2$$ so the coefficient of growth is $3/\pi^2=0.3039635509\ldots$