Project Euler Problem 99
Comparing two numbers written in index form like 2^{11} and 3^7 is not difficult, as any calculator would confirm that 2
Solution
Answer: 709
1. Mathematical analysis
We want to determine which line of the file contains the largest value of
$$a^b$$
where each line contains a base/exponent pair $(a,b)$.
A direct comparison is impossible because numbers such as
$$632382^{518061}$$
contain millions of digits.
The key observation is that logarithms preserve order.
If
$$x > y,$$
then
$$\log(x) > \log(y).$$
So instead of comparing
$$a^b \quad \text{and} \quad c^d,$$
we compare their logarithms:
$$\log(a^b) = b\log(a)$$
and
$$\log(c^d) = d\log(c).$$
Thus,
$$a^b > c^d \iff b\log(a) > d\log(c).$$
This transforms an impossible comparison of gigantic integers into a comparison of ordinary floating-point numbers.
Example from the problem
Compare:
$$632382^{518061} \quad \text{vs} \quad 519432^{525806}$$
We compare:
$$518061\log(632382)$$
and
$$525806\log(519432).$$
The larger logarithmic score corresponds to the larger exponential value. This avoids ever computing the huge numbers themselves.
2. Python implementation
from math import log
# Read the file
with open("base_exp.txt") as f:
lines = f.readlines()
max_value = float("-inf")
max_line = 0
# Enumerate starting at 1 because Project Euler line numbers are 1-based
for line_number, line in enumerate(lines, start=1):
base, exponent = map(int, line.strip().split(","))
# Compare exponent * log(base)
value = exponent * log(base)
if value > max_value:
max_value = value
max_line = line_number
print(max_line)
3. Code walkthrough
Import logarithm
from math import log
We use the natural logarithm. Any logarithm base works because changing bases only multiplies every value by the same constant.
Read the input file
with open("base_exp.txt") as f:
lines = f.readlines()
Loads all 1000 base/exponent pairs.
Each line looks like:
632382,518061
Track the maximum
max_value = float("-inf")
max_line = 0
We store:
- the largest logarithmic score seen so far,
- the corresponding line number.
Process each line
for line_number, line in enumerate(lines, start=1):
start=1 matters because Euler asks for the line number, not zero-based indexing.
Parse base and exponent
base, exponent = map(int, line.strip().split(","))
Converts something like:
632382,518061
into integers:
base = 632382
exponent = 518061
Compute comparison metric
value = exponent * log(base)
Because:
$$\log(a^b)=b\log(a)$$
This gives a comparable score without constructing the huge number.
Update maximum
if value > max_value:
max_value = value
max_line = line_number
Whenever we find a larger exponential value, we remember its line number.
Small-example verification
The problem says the first two lines are:
$$632382^{518061}$$
and
$$519432^{525806}$$
Computing:
$$518061\log(632382)$$
vs.
$$525806\log(519432)$$
shows the first quantity is larger, confirming:
$$632382^{518061} > 519432^{525806}.$$
So the method behaves correctly on the provided example.
4. Final verification
- We never compute enormous powers directly (avoids overflow).
- Logarithms preserve ordering, so the comparison is mathematically exact for ranking.
- We scan all 1000 entries once, so runtime is tiny.
- The known computed result for the Euler dataset is line 709.
Answer: 709