 # 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 (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. ### Posted by Kristian SuprDewd

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? Kristian

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 Khaur

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

First you can compute the best possible outcome before exponentiating the number ([latex]9\log(A^B)=9B\log(A)[/latex]). 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. Kristian

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

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 🙂 Kristian

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 🙂 safety0ff

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

my result is 534, dont understand whats wrong…
digitSum(45^95)-534
wich numbers are that give digitSum(a^b)=972? 