// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (19 votes, average: 4.79 out of 5)
Loading...

Project Euler Solutions

Project Euler 99 Solution

Project Euler 99 Solution

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 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 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 ax, but using an identity to avoid calculating the ax argument:

\log a^x = x \times \log a

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 109.

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 99 Solution

Runs < 0.050 seconds in Python 2.7.

download arrowUse this link to get the Project Euler 99 Solution Python 2.7 source.

Afterthoughts

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

Project Euler 99 Solution last updated

Discussion

No comments yet.

Post a comment