Problem 99 — Largest Exponential

solved Sat, 19 Jul 2025, 15:42 · level 2 · difficulty 6% projecteuler.net github

ExponentiationMonotonic functionNatural logarithmArg maxPrefer closed form over iterationExploit symmetry and complementary counting

Comparing two numbers written in index form like $2^{11}$ and $3^7$ is not difficult, as any calculator would confirm that $2^{11} = 2048 \lt 3^7 = 2187$.

However, confirming that $632382^{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.

Problem Analysis

This problem asks me to compare one thousand numbers of the form base^exponent and identify which line holds the largest, where some of these numbers run to over three million digits. The naive approach - actually raising each base to its exponent and comparing the resulting integers - is hopeless: even with arbitrary-precision arithmetic, materializing a three-million-digit number takes substantial memory, and comparing two such numbers digit by digit is slow. The breakthrough is realizing that I do not need the values themselves, only their relative order. The logarithm is a strictly increasing function, meaning that for any positive numbers A and B, the relation A > B holds exactly when log(A) > log(B). Because the transform preserves ordering perfectly, ranking by logarithm gives the identical answer to ranking by the true values - with none of the cost.

Pairing this with the identity log(b^e) = e * log(b) collapses an intractable exponentiation into a single multiplication. To rank b^e I only need e * log(b), an ordinary floating-point number comparable in constant time. The whole algorithm is therefore a single linear scan over the N = 1000 lines, doing one logarithm and one multiply per line while tracking the running maximum - an O(N) procedure with a tiny constant factor. The one thing I must verify is precision: a 64-bit double-precision float carries roughly 15-16 significant decimal digits, far more than enough to separate 1000 distinct candidates whose log values differ well beyond rounding noise.

Solution Approach

Logarithmic Linear Scan (Python and C)

Both p0099_s0.py and p0099_s0.c implement the same algorithm; they differ only in language mechanics. The steps are:

  • Read the file: A runner helper (get_text_file) resolves the resource locally and loads its contents into memory. Reading the whole 22K file at once is trivial and avoids per-line I/O overhead.
  • Parse each line: Each line splits on the comma into an integer base and an integer exponent. Blank or malformed lines are skipped with a warning rather than aborting, which keeps the code robust to trailing newlines and Windows-style line endings.
  • Compute the ranking value: For each pair I compute log_val = exponent * log(base). By the identity log(b^e) = e * log(b), this is exactly the logarithm of the full power - the surrogate that ranks identically to the real value.
  • Track the argmax: Two state variables - the best value seen so far and the line that produced it - update whenever a larger value appears. This finds not merely the maximum but the line number achieving it, in a single pass.
  • Return the 1-based line number: Since the answer is a line number, Python uses enumerate(numbers, start=1) and C maintains an explicit line_num counter.

The differences are purely mechanical. The Python version retains the winning base and exponent so a --show flag can print a human-readable summary, including an estimated digit count via max_val / log(10). It uses splitlines to normalize line endings and a try/except block around parsing. The C version tokenizes the buffer with strtok_r, manually strips a trailing \r, splits on the comma with strchr, and parses each field with atoll. Both convert from integers to double only at the moment the logarithm is taken.

workbench

Test cases

categoryinputanswer
main file_url = https://projecteuler.net/resources/documents/0099_base_exp.txt 709

Results

solutioncategoryanswerverdict avg seconds cavg seconds py
p0099_s0 main 709 correct 0.000058 (63) 0.000361 (63)

Files

Tags & blogs

domain Exponentiation
technique s0 Monotonic functionNatural logarithmArg max
takeaway Prefer closed form over iterationExploit symmetry and complementary counting