Counting Fractions in a Range

Consider the fraction, $\dfrac n d$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\operatorname{HCF}(n, d)=1$, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for $d \le 8$ in ascending order of size, we get:
$$\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \mathbf{\frac 3 8, \frac 2 5, \frac 3 7}, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8$$
It can be seen that there are $3$ fractions between $\dfrac 1 3$ and $\dfrac 1 2$.
How many fractions lie between $\dfrac 1 3$ and $\dfrac 1 2$ in the sorted set of reduced proper fractions for $d \le 12\,000$?

The problem requires us to count the number of reduced proper fractions that lie between 1/3 and 1/2 when the denominator is less than or equal to 12,000.

Between any two fractions a/b and c/d, there is a mediant fraction (a+c)/(b+d). This fractions lies between a/b and c/d. If we have two fractions a/b < c/d, and if the mediant fraction (a+c)/(b+d) is a reduced fractional representation, then it is a member of the increasing sequence of the set of all reduced fractions. Now, we know that 1/3 < 1/2. So, we can take the mediant of these two, obtaining: (1+1)/(2+3) = 2/5, which is within the boundary of 1/3 and 1/2. Now we have two pairs of fractions (1/3 and 2/5) and (2/5 and 1/2) and repeat the process. We also make sure our denominator does not exceed 12,000. Continuing this way we end up with two ordered sets of fractions (with both denominators and numerators in ascending order), which are, on the left of 2/5 (closer to 1/3) : 1/3, 4000/11999, 3999/11998, 3998/11997... And on the right of 2/5 (closer to 1/2): 2/5, 3/5, 4001/10000, 4002/10001... Counting the number of fractions in both lists and summing them up, you will find that there are 726 fractions between 1/3 and 1/2 for d ≤ 12,000. Please note that this method is relatively efficient because it uses the property of mediant fractions to create a binary search method, which is much faster than just listing out all possible fractions up to 12,000 and counting which ones lie in the interval.

More Answers: