finite fractions density (represented with 2 finite integers) I'm trying to compare 2 types of data in programs: floating point decimals ($doubles$) and fractions (let's say $pair<long,long>$), but it doesn't really matter for the question.
So here is what I can't find nor do: I would like a exact expression, a good aproximation or a fast calculation O(1) of how many fractions are between numers 's' and 't'. To make this easy, let's say $0 \leq s,t \leq M$ where M is the max number both numerator and denominator can be.
Something like "$\#\{\frac{a}{b}\}$ with $0\leq a,b \leq M \land \frac{a}{b} \geq s \land \frac{a}{b} <t$ " (0 < b).
I can't find anything like that because I need to discard the different representations of the same number ( $\#\{\frac{1}{2}, \frac{2}{4}\} = 1$ ) and gcd(a,b) is very slow to make a code with it.
Another naive idea is $\#\{\frac{a}{b}\} = \frac{[primes]_1}{[primes]_2}$ where $[primes1]\cap[primes2] = \emptyset \land 0 \leq \prod[primes]_{1,2} \leq M \land s \leq \frac{[primes]_1}{[primes]_2} < t$
Again, i don't think i can do a good expression with that and to have a code checking for primes or sets is very slow.
Any ideas?
 A: Put each fraction $a/b$ at $(a,b)$ in the plane.  That gives a square of side length $M$.  
The proportion of fractions that are in lowest terms is $6/\pi^2\approx 0.6079$.  Here's why:  


*

*A quarter of fractions have even numerator and denominator.  Throw them away, leaving 3/4 of fractions.  

*A ninth of fractions that remain have numerator and denominator divisible by 3.  Throw them away, now only $(3/4)\times(8/9)$ remain.  

*All fractions with numerator and denominator multiples of 4 have already been thrown away because they are even.  

*Throw away $1/25$ of the remainder, then $1/49$, $1/121$ and so on.  The fraction that remains turns out to be $$\frac34\frac89\frac{24}{25}\frac{48}{49}\cdots=\frac6{\pi^2}$$


If $s<a/b<t<1$, then $(a,b)$ is within the triangle whose vertices are  $(0,0),(sM,M),(tM,M)$.  Its area is $M^2(t-s)/2$
If $1<s<t$, the triangle has vertices $(0,0),(M,M/t),(M,M/s)$.
If $s<1<t$, you have two triangles, with the vertex $(M,M)$ included.
Then, since only $6/\pi^2$ of fractions are in lowest terms, multiply the area by $6/\pi^2$.  So the first case gives about $3M^2/\pi^2$ fractions.
There is some variation near the simplest rational numbers.  For example, if $M=1000$, there is only one fraction between 0.4995 and 0.5005.  That gives an error term of size $M$, compared to the formula which has size $M^2$.
