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]

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: