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!

(Don’t) Plug in to the future

Latest leaks online suggest Apple is going to the ship the soon-to-be-launched iPhone 12 with no chargers and ear-pods in the box. This has caused widespread debate in the online community; some call it a pure money-grab move from Apple and some consider it a sensible move. Let’s dive deeper into it and see.

Continue reading “(Don’t) Plug in to the future”

Project Euler #99

Click here to read the original problem

So the main challenge here was to be able to compare two different exponents (very large ones) like 632382518061 and 519432525806. 100 such had to be compared and the greatest to be found. To compute even one can take a decent machine several minutes, let alone 100 of these. Even if you do go by the long road, you end up comparing values stored with fixed accuracy (significant figures) in scientific form – something python does automatically for very large numbers like these.

Hence, to simplify calculations I did some algebraic manipulations, using logarithms. Take two exponents such that a^b > c^d. For all a,b\geq0, we can take the natural log of both sides and not change the equation (the sign to be specific), resulting in – b\log(a) > d\log(c). We already know that our assumption about a and b is true for the given data, thus, we can continue to calculate the product of the exponent part and the natural log of the base of each number. For whichever datum this is the greatest, is in turn the greatest number of the lot.

With this method, I was able to achieve an execution time of 0.007 seconds. That is fast enough!

Output Screenshot
[The answer portion has been blacked out]
Create your website with WordPress.com
Get started