finite fractions density (represented with 2 finite integers)

Question

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?

Answer 1

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$.