# 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?

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

• Well.. this is a bit above my understanding xD. I don't know how to make with this an algebraic/computational resolution. Also, if you use points (a,b) to calculate the amount of fractions, i think you keep counting several times the same fractions, but i'm not sure. Another thing: if you are aproximating with the 61%, that's a huge miss. – Pernoctador Jan 8 '18 at 1:43
• The square contains all the fractions. The area of the triangle is $M^2(t-s)/2$ is all fractions $s<a/b<t<1$. Then multiply by $6/\pi^2$ to reject repeats. – Michael Jan 8 '18 at 2:02
• Alright. I've been thinking a lot about this. Yesterday I was sure I found a mistake in your formula, but I'm not sure anymore xD. What make me think it's not right is the fact you use the area of the triangle. To me, I should count the amount of "dots" $a,b$ in the triangle. However in the example of M=6, s=0 and t=1 (the answer is 13), the area is 18 and so your answer is aprox 11. If I count the dots in the triangle, I have 28, and so my answer would be 17, wich is further away. Can you explain me why this happens? – Pernoctador Jan 14 '18 at 20:31