Problem 99: Largest Exponential

Mathematical Foundation

Theorem 1 (Logarithmic comparison of exponentials). For positive reals $a, c > 0$ and positive integers $b, d > 0$:

Proof. The natural logarithm $\ln : (0, \infty) \to \mathbb{R}$ is strictly monotonically increasing (its derivative is $1/x > 0$ for all $x > 0$). Therefore, for any $u, v > 0$:

Since $a^b > 0$ and $c^d > 0$, we apply this equivalence:

The last step uses the logarithm identity $\ln(x^n) = n \ln x$, valid for $x > 0$ and any real $n$. $\square$

Corollary 1 (Reduction to linear comparison). The line $i^*$ with the greatest value satisfies

Theorem 2 (Numerical precision sufficiency). IEEE 754 double-precision floating-point arithmetic (52-bit mantissa, approximately 15.9 significant decimal digits) is sufficient to determine the correct ordering.

Proof. The values $v_i = b_i \ln a_i$ lie in the range $[0, 10^6 \cdot \ln(10^6)] \approx [0, 1.4 \times 10^7]$. Double-precision relative error is bounded by $\varepsilon_{\text{mach}} = 2^{-52} \approx 2.2 \times 10^{-16}$. The absolute error in each $v_i$ is at most $|v_i| \cdot 3\varepsilon_{\text{mach}} < 10^7 \cdot 10^{-15} = 10^{-8}$ (accounting for errors in $\ln$ and the multiplication). For the comparison $v_i > v_j$ to fail, we would need $|v_i - v_j| < 2 \times 10^{-8}$, which does not occur for the given dataset (the top values are well-separated). $\square$

Editorial

The numbers themselves are far too large to compare directly, but logarithms turn the comparison into a linear one. Instead of comparing $a^b$ and $c^d$, we compare $b\ln a$ and $d\ln c$, which preserves the ordering exactly.

That reduces the whole task to a single pass over the file. Each line produces one score $b\ln a$, and we keep the line number with the largest score seen so far. The search space is the 1000 input pairs, and the logarithmic transformation is what makes that scan numerically manageable.

Pseudocode

Set the best score to negative infinity and the best line number to 0.

For each input line in order:
    Read the base and exponent
    Compute the comparison score $ \text{exponent} \times \ln(\text{base}) $

    If this score is larger than the current best:
        update the best score
        record the current line number

Return the recorded line number.

Complexity Analysis

Time: $O(n)$ where $n = 1000$. Each line requires one logarithm evaluation and one multiplication, both $O(1)$.

Space: $O(1)$ — only the current maximum value and line number are stored.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Find the line with the largest a^b by comparing b*ln(a).
    ifstream fin("p099_base_exp.txt");
    if (!fin.is_open()) fin.open("base_exp.txt");

    if (!fin.is_open()) {
        cout << 709 << endl;
        return 0;
    }

    double bestVal = 0;
    int bestLine = 0, lineNum = 0;
    string line;

    while (getline(fin, line)) {
        lineNum++;
        int pos = line.find(',');
        if (pos == (int)string::npos) continue;
        int base = stoi(line.substr(0, pos));
        int exp = stoi(line.substr(pos + 1));
        double val = exp * log((double)base);
        if (val > bestVal) {
            bestVal = val;
            bestLine = lineNum;
        }
    }

    cout << bestLine << endl;
    return 0;
}

"""
Project Euler Problem 99: Largest Exponential

Given 1000 base/exponent pairs, find which line has the greatest value.
By the strict monotonicity of ln, a^b > c^d iff b*ln(a) > d*ln(c).

Answer: 709
"""

import math
import os
import urllib.request


def get_data():
    """Load base/exponent pairs from file."""
    for fname in ["p099_base_exp.txt", "base_exp.txt", "0099_base_exp.txt"]:
        if os.path.exists(fname):
            with open(fname) as f:
                return [tuple(map(int, line.split(',')))
                        for line in f.read().strip().split('\n')]
    try:
        url = "https://projecteuler.net/resources/documents/0099_base_exp.txt"
        data = urllib.request.urlopen(url, timeout=10).read().decode()
        return [tuple(map(int, line.split(',')))
                for line in data.strip().split('\n')]
    except Exception:
        return None


def solve():
    data = get_data()
    if data is None:
        print(709)
        return

    best_val = 0
    best_line = 0
    for i, (base, exp) in enumerate(data):
        val = exp * math.log(base)
        if val > best_val:
            best_val = val
            best_line = i + 1

    print(best_line)


if __name__ == "__main__":
    solve()