Project Euler: Problem 56 – Powerful digit sum

Problem 56:

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?

Idea:

I was wondering how long it was going to be until googol came up in a problem (although I was part expecting googolplex)
 
I didn’t see any easy way to do this, as it’s pretty straight forward, raise a to the power of b, for all possible combinations of a and b < 100, take the sum of the digits, and repeat until you reach 9999, keeping track of the maximal sum.

int answer = -1;

for(int a = 1; a < 100; a++) {
   for(int b = 1; b < 100; b++) {
      BigInteger base = BigInteger.valueOf(a);
      BigInteger result = base.pow(b);
      int[] digits = EulerUtils.numberToDigits(result.toString());
      int sum = 0;
      for(int i : digits) {
         sum+=i;
      }
      if(sum > answer) answer = sum;
   }
}
Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *