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^{100}) is a massive number: one followed by one-hundred zeros; 100^{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, where^{b}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.

Greeings!

And also:

Do you get a speed up if you replace

with:

in the digit sum method?

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

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.

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

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 🙂

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 🙂

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.

my result is 534, dont understand whats wrong…

digitSum(45^95)-534

wich numbers are that give digitSum(a^b)=972?

please help

I was hoping for a mathematical revelation on this problem. Learned a lot about modular exponentiation from Wikipedia as I was trying to figure out how to calculate each digit of a^b using mod 10 operators. Good way to get the first digit of the number, but the next divide by 10 to reduce the number didn’t seem simple. Finally, I broke down and used C# BigInteger, where the answer is trivial to find, and all the posted optimizations are somewhat obvious. Still, it left me feeling disappointed there wasn’t a less brute-force way of calculating the answer. BTW, I used the BigInteger.DivRem() method to get each digit, just like you would do in C.