Project Euler Problem 99 Solution

Question

Comparing two numbers written in index form like 2112^{11} and 373^7 is not difficult, as any calculator would confirm that 211=2048<37=21872^{11} = 2048 \lt 3^7 = 2187.

However, confirming that 632382518061>519432525806632382^{518061} \gt 519432^{525806} 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.

Commentary

As the question notes, it would be difficult to evaluate these exponents directly as they contain over three million digits each. Therefore, we must find a way to reduce these exponents to a manageable size.

To do so, we use the identity logax=x×loga\log{a^x} = x \times \log{a}. Since logb>loga\log{b} \gt \log{a} if $ b a$, this will serve as an approximation of calculating the exponents directly.

Python

#!/usr/bin/env python
import os
from math import log10
largest = [0, 0]
for i, line in enumerate(open(os.path.join(os.path.dirname(__file__), 'base_exp.txt'))):
    a, x = list(map(int, line.split(',')))
    if x * log10(a) > largest[0]:
        largest = [x * log10(a), i+1]
print(largest[1])
$ time python3 largest-exponent.py
real   0m0.025s
user   0m0.020s
sys    0m0.004s

Questions? Comments? Send me an email: [email protected]