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

I thought of two solutions for Problem 99 of Project Euler. One which I knew would be reasonably fast and the other one which I was curious about. The latter one is completely intractable though. The problem reads

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.

At first I thought it would be fun to see how the BigInteger class would fare in this problem. The answer is not so well. In fact calculating the first number alone takes 167s which is already above the 1 minute allowed limit for the problems, let alone calculate all thousands of the numbers.

The second approach I took was using logarithms. One of the rules of logarithms is the power rule which states

So instead of calculating the power, we can take a logarithm of any base and convert the problem to a multiplication problem. Which means that the problem has been reduced to taking the logarithm and multiply that by a number.

The code for that can be written in C# as

int maxline = 0;
double maxnum = 0;
string[] lines = File.ReadAllLines(filename);
for (int i = 0; i < lines.Length; i++) {
    string&#91;&#93; line = lines&#91;i&#93;.Split(',');
    double basenum = Math.Log(Convert.ToInt32(line&#91;0&#93;));
    int exponent = Convert.ToInt32(line&#91;1&#93;);
    double number = basenum * exponent;
    if (number > maxnum) {
        maxline = i+1;
        maxnum = number;
    }
}

This code, unlike the first appraoch runs in

The line with the largest number is 709
Solution took 1,3466 ms

Wrapping up

Only one more problem to go till we reach 100 and even though this particular problem was actually rather easy. The source code for problem 99 can be found here.

Did you solve it another way?

Posted by Kristian

8 comments

Bjarki Ágúst

A similar but much harder problem is as follows:

Given an integer [latex]n > 2[/latex] and two integer sequences [latex]a_1, a_2, \cdots, a_n[/latex] and [latex]b_1, b_2, \cdots, b_n[/latex] where [latex]1 \le a_i, b_i \le 100[/latex], determine which of the expressions [latex]a_1^{a_2^{\cdot^{\cdot^{a_n}}}}[/latex] and [latex]b_1^{b_2^{\cdot^{\cdot^{b_n}}}}[/latex] has the greatest numerical value.

Source: ALGORITHM PROBLEMS FOR DUMMIES: PETR MITRICHEV’S BLOG.

I guess that the challenge here lies within the precision of the solution. At least according to the blog. Because if you had infinite precision you should be able to use the same approach as in this problem.

Bjarki Ágúst

Precision may or may not be the problem, but at least the approach we’re using here won’t work.

You may by thinking about doing it like this, but it’s easy to see that this is wrong. You can try deriving it, but after a few steps you encounter [latex]\log{a + b}[/latex] which he wrongly assumes is [latex]\log{a} + \log{b}[/latex].

I still haven’t found a valid solution. Petr thought he had a valid solution, but he still hasn’t published it (he may have realized it was wrong).

More discussion can be found here.

No it wasn’t based on that, and yes I can see that he makes a wrong assumption there.

I just thought that you could apply the log repeatedly such that if you have [latex]a^{b^c}[/latex] you could end up with [latex]log(a)b^c[/latex] and then my logic started to fail.

However, I think that we might make this overly complicated since [latex]a^{b^c} = a^{bc}[/latex]. I know you will end up with a potentially very large factor, but you could rather easily make a prime factorization of it (due to all components being factored into divisors less than 100). Then you can start weeding out common factors of the two exponents. Since you can make [latex]a^{b’^{c’}}[/latex] where c’ is the gcd of the exponents on both sided.

After that you “just” need to figure out which of [latex]a^{b’}[/latex] is bigger. I am uncertain whether this helps or not.

Bjarki Ágúst

Many people get this wrong, and I probably should have stated it explicitly.

[latex]a^{b^c}[/latex] is right associative. Computing [latex]2^{3^4}[/latex] is the same as computing [latex]2^{81}[/latex] (because [latex]3^4 = 81[/latex]).
So [latex]2^{3^4}[/latex] is not [latex]2^{3 \times 4} = 2^{12}[/latex].

But if we were evaluating the tower like you thought, your method would have been correct. But that problem is a lot easier than this one.

(It’s also funny how you get the order right when you’re taking the logarithm, but get it wrong in the next paragraph.)

Yes I see that now… I should have thought that a bit more through before talking. Anyway interesting problem which I need to follow the discussion for.

Zsolt Szilagyi

Did you confirm this solution?
Comparing 1^100,2^99, 3^97… with 1*100,2*99,3*98… I find that 24^76 is way bigger than 50^50, while 50*50 is way bigger than 24*76. They have completely different maxima, so simply multiplying the results does not seem to work. Should’n in the line “double number = basenum * exponent;” be an exponent invoked?

Thanks!

Zsolt: read the source again. He is not multiplying doing 50 * 50, but Math.Log(50) * 50 and Math.Log(24) * 76.

Leave a Reply