Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

logarithm
communitycreator

How to solve Project Euler 99

Armaan Nougai

Problem statement

Let the five lines below be the content of a text file.

5,2
6,9
4,10
10,2
5,3

These are base-exponent pairs, separated by a comma. We have to find which line will have maximum value after the execution of the mathematical expression, that is, base^exponent.

The first line evaluates to 5^2, that is, 25. The second line gives 6^9, that is, 10077696. Similarly, the third line gives 1048576, the fourth line gives 100, and the fifth line gives 125.

Out of these five base-exponent pairs, the pair on the second line evaluates to the maximum value, 10077696. Hence, the answer is line two.

Now, we have to find out which line evaluates to the maximum value amongst 1000 lines.

The largest exponential

The text file given below contains one thousand lines with a base-exponent pair on each line. We have to determine which line number has the greatest numerical value.

p099_base_exp.txt

Solution approach

The hurdles in solving this problem with brute force are that both the base and exponent are quite large numbers, and the power operation itself is a time-consuming task.

However, for this problem, we don’t have to calculate each value, we just need to compare them.

Alternative way of comparing two base-exponent pairs.

 first pair = (a,b)
 firstValue = a^b

 second pair = (c,d)
 secondValue = c^d

According to the power property of logarithms, log(x^y) = y*log(x).

If firstValue>secondValue, and we take log on both sides then.

=> log(firstValue) > log(secondValue).

=> log(a^b) > log(c^d)

=> b* log(a) > d* log( c)

We’ll replace the base^exponent operation with exponent*log(base). This change will largely reduce execution time as the second operation is essentially only the multiplication of two quantities.

Note: Paste the contents of the text file given above in the input box to run the code.

from math import log

with open('__ed_input.txt','r') as FILE: 
    cnt=1
    maxValue=0
    maxIndex=0
    
    while (cnt<=1000):
        base,exponent = list(map(int,FILE.readline().split(',')))
        value = exponent*log(base)
        
        if maxValue<value:
            maxValue = value
            maxIndex = cnt
        
        cnt+=1


print(maxIndex)

Enter the input below to be saved in file __ed_input.txt

Python code

Code explanation

  • In line 1, we import the log function from the math library.

  • In line 3, we open a file named “__ed_input.txt” as FILE. This file contains the input text.

  • In lines 4-6, cnt is the variable which represents the line numbers and is used to traverse through the data. maxValue is the variable that stores the maximum value of the base-exponent pair. And maxIndex stores the line number, where the maxValue occurs.

  • In lines 8-16, we We start the while loop till the cnt<=1000.

    • In line 9, we take the (base, exponent) pair as input from FILE.

    • In line 12-14, we update the values of maxValue and maxIndex. If maxValue< value.

    • In line 16, we increment the line number, that is, cnt.

  • In line 19, as maxIndex contains the line number of where maxValue occurred, we print maxIndex.

RELATED TAGS

logarithm
communitycreator
RELATED COURSES

View all Courses

Keep Exploring