0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Pernoctador Jan 8 '18 at 1:43
  • $\begingroup$ 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. $\endgroup$ – Michael Jan 8 '18 at 2:02
  • $\begingroup$ 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? $\endgroup$ – Pernoctador Jan 14 '18 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.