Ordered fractions
In this post we will look at solving Project Euler's problem #71, which is about ordered fractions. I have been puzzling with pen and paper for a while during this problem, and researching about fractions really paid off big time for this problem. The final solution is pretty elegant in my opinion. Let's get into it! Problem statement Consider the fraction $n / d$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\text{GCD}(n, d) = 1$, it is called a reduced proper fraction. If we list the the set of reduced proper fractions for $d \leq 8$ in ascending order of size, we get: 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 It can be seen that $2/5$ is the fraction immediately to the left of $3/7$. By listing the set of reduced proper fractions for $d \leq 1,000,000$ in ascending order of size, find the numerator of the fraction immediately to the left of $3/7$. Naive approach As
