Problem #99 concerns comparing large exponential numbers. The question reads:
Project Euler Problem 99: Largest exponential Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187. However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits. Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value. NOTE: The first two lines in the file represent the numbers in the example given above.
With a minimal knowledge of mathematics, this problem is quite easy for its placement. Here is my solution:
Solution #1: Logarithm Approach
Because log(x) is an increasing function, log(x)<log(y) implies x<y and vice versa. It is well known that log(a^b) = b*log(a). Thus, the lines can easily be sorted by the value of b*log(a) and the maximal line can be found. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Logarithm Approach to Project Euler Problem #99
'''
import time
from math import log
f = open("PE99Exponents.txt","r")
if(f.mode == "r"):
contents = f.readlines()
realContents = []
for x in contents:
realContents.append(map(int,x.split(",")))
else:
raise ValueError("Cannot read from file")
def projectEulerProblemNinetyNine(myList):
a = sorted(myList, key = lambda x: x[1]*log(x[0]))
return myList.index(a[len(a)-1])+1
start = time.time()
print projectEulerProblemNinetyNine(realContents)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
709
--- 0.000494003295898 seconds ---
for input of given list of exponents.
'''
And with that, we’re done. Looking back on it, my solution actually solves the more complex problem of sorting all of the lines. Its efficiency could be improved by searching specifically for the maximal line. I probably won’t return to make this change because the problem was so simplistic.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 