Problem 99: Largest Exponential

Project Euler Problem 99 Solution

EulerSolve provides an optimized solution for Project Euler Problem 99, Largest Exponential, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The input consists of 1000 lines, each containing a pair $(b,e)$ representing the number $b^e$. The task is not to compute the largest power itself, but to identify which 1-indexed line produces the largest numerical value. The obstacle is size. Even a single value such as $519432^{525806}$ is astronomically large, so ordinary exponentiation is the wrong mathematical object to work with. The real problem is a comparison problem: among all lines, which pair $(b_i,e_i)$ makes $b_i^{e_i}$ as large as possible? Mathematical Approach Let the $i$-th line contain $(b_i,e_i)$, and write $$x_i=b_i^{e_i}.$$ We want the line whose $x_i$ is maximal. The implementations do not build $x_i$ directly. Instead they replace each gigantic power by a much smaller real-valued score that preserves exactly the same ordering. Replacing Huge Powers by Logarithmic Scores For every positive base $b_i$, the natural logarithm is defined and satisfies $$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$ This suggests attaching to each line the score $$s_i=e_i\ln(b_i).$$ The line with the largest power is exactly the line with the largest score. No big integers are needed; the whole comparison has been reduced to ordinary floating-point arithmetic on numbers of manageable size. The base of the logarithm is irrelevant....

Detailed mathematical approach

Problem Summary

The input consists of 1000 lines, each containing a pair $(b,e)$ representing the number $b^e$. The task is not to compute the largest power itself, but to identify which 1-indexed line produces the largest numerical value.

The obstacle is size. Even a single value such as $519432^{525806}$ is astronomically large, so ordinary exponentiation is the wrong mathematical object to work with. The real problem is a comparison problem: among all lines, which pair $(b_i,e_i)$ makes $b_i^{e_i}$ as large as possible?

Mathematical Approach

Let the $i$-th line contain $(b_i,e_i)$, and write

$$x_i=b_i^{e_i}.$$

We want the line whose $x_i$ is maximal. The implementations do not build $x_i$ directly. Instead they replace each gigantic power by a much smaller real-valued score that preserves exactly the same ordering.

Replacing Huge Powers by Logarithmic Scores

For every positive base $b_i$, the natural logarithm is defined and satisfies

$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$

This suggests attaching to each line the score

$$s_i=e_i\ln(b_i).$$

The line with the largest power is exactly the line with the largest score. No big integers are needed; the whole comparison has been reduced to ordinary floating-point arithmetic on numbers of manageable size.

The base of the logarithm is irrelevant. Using $\log_{10}$, $\ln$, or any other logarithm only multiplies every score by the same positive constant, so the winning line does not change. The implementations use the standard natural logarithm provided by each language runtime.

Why This Comparison Is Exact

The crucial fact is that $\ln$ is strictly increasing on positive real numbers. Therefore, for any two lines $i$ and $j$,

$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$

Likewise, equality of the original powers would give equality of the logarithmic scores. So the transformation does not approximate the ordering; it preserves it exactly. The only approximation occurs in the numerical evaluation of the logarithm, not in the mathematics of the reduction.

Worked Comparisons

A small checkpoint makes the idea transparent. Compare $2^{11}$ and $3^7$. Their scores are

$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$

Since $7\ln 3$ is larger, we conclude $3^7 > 2^{11}$, exactly as expected.

The same method handles the larger comparison quoted in the problem discussion. Compare

$$632382^{518061}\quad\text{and}\quad 519432^{525806}.$$

The corresponding scores are

$$518061\ln 632382 \approx 6919869.733217769$$

$$525806\ln 519432 \approx 6919865.228473604.$$

The first score is larger, so

$$632382^{518061} > 519432^{525806}.$$

This is exactly the kind of comparison performed for every line in the dataset.

The Running-Maximum Invariant

Once each line is represented by $s_i$, the remaining task is a simple maximum search. After processing the first $k$ lines, maintain the invariant:

$$\text{the stored line number is the line with the largest score among } s_1,s_2,\dots,s_k.$$

When line $k+1$ is read, compute its score $s_{k+1}$. If $s_{k+1}$ exceeds the current best score, replace the stored winner; otherwise keep the old one. By induction, the invariant remains true after every step, and after the final line the stored answer is the desired line number. If two scores were exactly equal, keeping the first one is consistent with the usual strict-update rule used by the implementations.

How the Code Works

Reading the Base-Exponent Pairs

The C++, Python, and Java implementations read the comma-separated input lines, split each line into a base and an exponent, and convert both parts into numeric values. Blank lines are ignored so that the scan only processes actual data rows.

Scoring Each Line

For every parsed pair $(b,e)$, the implementation computes the score $e\ln(b)$. That number is the logarithm of $b^e$, so it carries exactly the ordering information needed for the problem. The C++ implementation uses extended floating-point precision, while the Python and Java implementations use standard double-precision logarithms, but all three are evaluating the same mathematical quantity.

Keeping the Current Winner

The implementation stores only the best score seen so far and the corresponding 1-indexed line number. Each new score is compared with the current best; if it is larger, both stored values are updated. After the scan reaches the end of the list, the saved line number is printed as the answer.

Complexity Analysis

If the dataset has $n$ lines, the algorithm performs one logarithm, one multiplication, and one comparison per line, so the running time is $O(n)$. For Problem 99, $n=1000$, so the total work is tiny.

The mathematical core needs only $O(1)$ extra state: the current line number, the best score so far, and the best line number so far. Some implementations may read the small input into memory first because the file is tiny, but the comparison method itself is fundamentally a constant-space streaming scan.

Footnotes and References

Project Euler Problem 99: https://projecteuler.net/problem=99
Logarithm: Wikipedia - Logarithm
Natural logarithm: Wikipedia - Natural logarithm
Exponentiation: Wikipedia - Exponentiation
IEEE 754 floating-point arithmetic: Wikipedia - IEEE 754

Problem 99 source code

C++

#include <cmath>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>

namespace {

struct Options {
    std::string file = "resources/documents/0099_base_exp.txt";
    bool run_checkpoints = true;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

int solve_from_text(const std::string& text) {
    std::istringstream input(text);
    std::string line;

    int best_line = -1;
    long double best_score = -1.0L;
    int line_number = 0;

    while (std::getline(input, line)) {
        if (line.empty()) {
            continue;
        }

        ++line_number;
        std::size_t comma = line.find(',');
        if (comma == std::string::npos) {
            throw std::runtime_error("Malformed line in base/exp list");
        }

        const long double base = std::stold(line.substr(0, comma));
        const long double exponent = std::stold(line.substr(comma + 1));
        const long double score = exponent * std::log(base);

        if (score > best_score) {
            best_score = score;
            best_line = line_number;
        }
    }

    if (best_line < 0) {
        throw std::runtime_error("No data rows found in base/exp list");
    }

    return best_line;
}

int solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open base/exp file: " + file_path);
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();
    return solve_from_text(buffer.str());
}

bool run_checkpoints() {
    const std::string sample = "2,11\n3,7\n";
    if (solve_from_text(sample) != 2) {
        std::cerr << "Checkpoint failed for small base/exp sample" << '\n';
        return false;
    }

    const std::string statement_pair = "632382,518061\n519432,525806\n";
    if (solve_from_text(statement_pair) != 1) {
        std::cerr << "Checkpoint failed for statement comparison pair" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 99: Largest exponential
# Determine which line number has the greatest numerical value (base^exp).

import os, math

def solve():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, '..', 'resources', 'documents', '0099_base_exp.txt')
    with open(file_path) as f:
        lines = [line.strip() for line in f if line.strip()]
    
    best_line, best_val = 0, 0
    for i, line in enumerate(lines):
        base, exp = map(int, line.split(','))
        val = exp * math.log(base)
        if val > best_val:
            best_val = val
            best_line = i + 1
    print(best_line)

solve()

Java

import java.nio.file.*;
import java.util.*;

public class Euler99 {
    public static void main(String[] args) throws Exception {
        List<String> lines = Files.readAllLines(Path.of("resources/documents/0099_base_exp.txt"));
        int bestLine = 0;
        double bestVal = 0;
        for (int i = 0; i < lines.size(); i++) {
            String[] parts = lines.get(i).trim().split(",");
            if (parts.length < 2)
                continue;
            double val = Integer.parseInt(parts[1]) * Math.log(Integer.parseInt(parts[0]));
            if (val > bestVal) {
                bestVal = val;
                bestLine = i + 1;
            }
        }
        System.out.println(bestLine);
    }
}