Project Euler 56: Considering natural numbers of the form, a^b, finding the maximum digital sum.

Project Euler 56: Considering natural numbers of the form, a^b, finding the maximum digital sum.

Written by on 13 August 2011

Topics: Project Euler

Problem 56 of Project Euler is one of those problems where I really haven’t found a nice method for solving it. The problem description reads

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

I have only found a brute force solution with a bit of pruning, so lets jump right into that.

The first thing we need is a method to calculate the digit sum of a number. Since some of the numbers are pretty big I have chosen to keep everything in BigInteger, so the fastest C# method I can conjure up for calculating the digit sum is

private int DigitSum(BigInteger number) {
    char[] k = number.ToString().ToCharArray();
    int ds = 0;
    for(int i = 0; i < k.Length; i++){
        ds += Convert.ToInt32(k[i].ToString());
    }
    return ds;
}

Normally I would keep it all in numeric types, but when we are dealing with BigInteger, it is less costly to convert it to a char array and parse it to integers.

Once that is in place lets have a look at the main method. Doing it completely brute force would require us to check all 9801 combinations of a and b for 0 < a,b < 99.

However, if we start from a,b = 99 and work us downwards there is a good chance to find a large number. Once 9 times number of digits of a^b becomes smaller than the current result, it is safe to stop counting down. The number of digits can be found rather easily with the base 10 logarithm.

The C# code looks like

const int limit = 100;
int result = 0;

for (int a = limit-1; a > 0; a--) {
    for (int b = limit-1; b > 0; b--) {
        BigInteger number = BigInteger.Pow(a,b);
        if (((int)BigInteger.Log10(number)) * 9 < result) break;
        int sum = DigitSum(number);
        if (sum > result) result = sum;
    }
}

The result of the execution of the code is

The largest digit sum of a^b with a, b < 100 is 972
Solution took 95 ms

Compared to my first implementation where I kept the DigitSum in numeric types I had an execution time of 290ms.

Wrapping up

This post is a bit on the short side but I don’t have anything fancy to add to the solution. You can find the source code here.

Your comments are as always very welcome, be it other solution strategies, questions or just a greeting.

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

  1. SuprDewd says:

    Greeings!

    And also:
    Do you get a speed up if you replace

    ds += Convert.ToInt32(k[i].ToString());

    with:

    ds += k[i] - '0';

    in the digit sum method?

  2. Kristian says:

    Hi

    yes I get a significant speed up by using that way of doing it instead.

    I end up spending 29ms instead of 95ms. That is really a clever little thing. So instead of going through the hassle of converting the char to an int value, you just subtract the ascii value of 0, which is 48. Since 0-9 is next to each other in in the ascii table, you are left with the right value.

    Nice little trick.

    /Kristian

  3. Khaur says:

    I found two ways to trim the loops down a bit more.

    First you can compute the best possible outcome before exponentiating the number (). This allows us to skip about 60-70% of the iterations in practice.

    Secondly you can update your best possible outcome while computing the digit sum and give up on summing if it goes below the current maximum. This is a further 10% gain to me.

    Also, following in SuprDewd’s footsteps, you can factorize the part where you substractthe ASCII value of 0.

  4. Kristian says:

    You are right. Which in my case means that I could avoid invoking the big integer library until I have found suitable candidates. Nice.

  5. Shobhit says:

    This problem was trivial with BigInteger. I wonder what would I have done if I had to do it in C. I am planning to disassemble System.Numerics and see how this structure is implemented. It is really cool.
    The trick suggested by SuperDewd is a routine in C programming. I used to do it all the time. Now I go the easy way and convert it using library routines (and read the documentation every time).
    High level languages make you rusty :)

  6. Kristian says:

    I solved one of the early problems with my own “big Integer” implementation using arrays to store the number in. However, I got lazy as you say and exploited the possibilities the framework gives me :)

  7. safety0ff says:

    You can also skip all the a’s divisible by 10.

    The best outcome should be calculated as 9*b*ceil(log10(a)), you and Khaur forgot the ceil (note: it should be a+1 but since we’re skipping all a’s divisible by 10 we can omit the +1.)

    I doubt that Khaur’s suggestion of updating the best outcome calculation on the fly improves the performance very much, most of the running time should be spent in BigInt operations, typically the bigint to string conversion (depending on the implementation.)

    I tried some other optimizations but they did not yield much because my program is bound by the bigint to string conversion.

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.