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(\frac{n}{d}) 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.

Output Screenshot
[The answer portion has been blacked out]

This algorithm found the answer in 0.8 seconds!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: