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

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 (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ 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, a^b, 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.