Project Euler #71

Click here to read the original problem

After giving the problem a read, this is how I broke it down in my head. From the set $\{(n, d) \mid n<d, d\leq1000000\}$ find max() where $\frac{n}{d} < \frac{3}{7}$ . Let’s call $\frac{3}{7}$ target for simplicity. In order to do this efficiently I did not want to list down all the numbers as there would be $333332833333500000$ fractions to account for in that case. Instead I looked to find the fraction that would place to the immediate left of our target if it were included with all the fractions created with a certain value of d. That leaves us with 1e6 values to work with, significantly reducing the workload. So this value was determined using the simple simplification n = floor(target * d). This gives the largest integer n such that $\frac{n}{d} < \frac{3}{7}$ . All of these fractions are compared to find the largest one and that is our answer fraction. Before we finish, we must reduce this fraction to its simplest form. This is easily done by dividing the numerator with the GCF of the numerator and the denominator. The GCF can be calculated using the python math module’s function or using a self written function of acceptable efficiency. This quotient gives us the final answer.