Project Euler 99: Find the base/exponent pair in the file has the greatest numerical value

Project Euler 99 Problem Description

Project Euler 99: Comparing two numbers written in index form like 2¹¹ and 3⁷ is not difficult, as any calculator would confirm that 2¹¹ = 2048 < 3⁷ = 2187.

However, confirming that 632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶ 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.

Analysis

Knowing that the file of base and exponents pairs could produce a power with millions of digits, easily exceeding the usefulness of Python’s large integer support, a method has to be employed that determines the magnitude of the power with no regard to the actual value.

The best way to quickly determine this magnitude with the objective of finding the maximum power produced would be to find the log of a^x, but using an identity to avoid calculating the a^x argument:

Most of this program is opening a connection to the server, reading the file and finding the line number with the largest power.

Solving the HackerRank version of this problem requires the storage of all the magnitudes to a list to find the Kth smallest of them. Also the base and exponents can be as large as 10⁹.

This program and method
solves all test cases
on HackerRank

Project Euler 99 Solution

Afterthoughts

• Most of the time is spent reading the file from a remote URL.