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

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

Written by on 2 June 2012

Topics: Project Euler

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[] line = lines[i].Split(',');
    double basenum = Math.Log(Convert.ToInt32(line[0]));
    int exponent = Convert.ToInt32(line[1]);
    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?

6 Comments For This Post I'd Love to Hear Yours!

  1. Bjarki Ágúst says:

    A similar but much harder problem is as follows:

    Given an integer and two integer sequences and where , determine which of the expressions and has the greatest numerical value.

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

  2. Kristian says:

    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.

  3. Bjarki Ágúst says:

    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 which he wrongly assumes is .

    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.

  4. Kristian says:

    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 you could end up with and then my logic started to fail.

    However, I think that we might make this overly complicated since . 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 where c’ is the gcd of the exponents on both sided.

    After that you “just” need to figure out which of is bigger. I am uncertain whether this helps or not.

  5. Bjarki Ágúst says:

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

    is right associative. Computing is the same as computing (because ).
    So is not .

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

  6. Kristian says:

    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.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.