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.


Idea

Assume two pairs, $ (a_1, b_1) $, $ (a_2, b_2) $, $ m_1 = a_1^{b_1} $, $ m_2 = a_2^{b_2} $, then we can transfer the comparison of $ m_1 $ with $ m_2 $ to comparison of $ \frac{m_1}{m_2} $ with 1.

And it is easy to transfer to comparions of $ \log\frac{m_1}{m_2}$ with 0, which means $ \log{m_1} - \log{m_2} $ with 0, which means $ b_1 * \log{a_1} - b2 * \log{a_2} $ with 0.

So the greatest numerical value is the one with greatest value of $ b * \log{a} $


In [1]:
import sys, os; sys.path.append(os.path.abspath('..'))
from timer import timethis
from urllib.request import urlopen
from math import log
In [2]:
with urlopen('https://projecteuler.net/project/resources/p099_base_exp.txt') as f:
    resp = f.read().decode('utf-8')
In [3]:
pairs = [tuple(map(int, line.split(','))) for line in resp.splitlines()]
In [4]:
pairs[:5]
Out[4]:
[(519432, 525806),
 (632382, 518061),
 (78864, 613712),
 (466580, 530130),
 (780495, 510032)]
In [5]:
@timethis
def solve():
    return max(enumerate(pairs, 1), key=lambda enu: enu[1][1] * log(enu[1][0]))
In [6]:
solve()
Run for 0.000 seconds
Out[6]:
(709, (895447, 504922))