Project Euler

Problem 56: Powerful Digit Sum

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?

The Catch

Even with the help from Java's BigInteger class, looping from a = b = 2 to a = b = 99 (That's 98 * 98 = 9604 iterations) is very costly; the search range needs to be minimized.

The Light

Knowing how many digits the number a^b has without having to calculate its actual value is going to be very useful. To achieve this, use the formula (int)(b * log a) + 1. For example, the number 81² has (int)(2 * log 81) + 1 = (int)3.90848501888 + 1 = 3 + 1 = 4 digits.

Another useful concept is Expected Digit Sum, which can be calculated by multiplying the number of digits by 4.5. The reason: 4.5 is the mean of all digits ((0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)/10 = 45/10 = 4.5). So if these digits are distributed equally within a number, then the number's digit sum can be approximated by the mentioned formula.

For example, the number 1234567890 has 10 digits and its expected digit sum is 10 * 4.5 = 45 and its actual digit sum is 45. The number 123456789 has 9 digits and its expected digit sum is 9 * 4.5 = 40.5 and its actual digit sum is 45. This is a fairly good estimation for larger numbers.

Using these concepts, consider the number 90⁹⁰, which has 176 digits and whose expected digit sum is 792 and the number 90⁹⁹, which has 194 digits and whose expected digit sum is 873. Generally, more digits means greater digit sum. It can be seen that the maximum digit sum is not in the range from a = b = 2 to a = b = 90 (because 90⁹⁹ has more digits and thus a greater digit sum than 90⁹⁰). Thus, it is safe to start the search range from a = b = 90.

Having the search range minimized, a brute force approach can be implemented using Java's BigInteger class. Use the discussion about ASCII values in Problem 22 to tweak the method that calculates the digit sum.

The Code

import java.math.*;

public class Problem56
{
  public static void main(String[] args)
  {
    int max = 0;

    for(int a = 90; a <= 100; a++)
    {
      for(int b = 90; b <= 100; b++)       
      {
        BigInteger base = new BigInteger(Integer.toString(a));         
        BigInteger tmp = base.pow(b);            
        int digitSum = digitSum(tmp.toString());             
        if(digitSum > max)
          max = digitSum;
      }
    }
    System.out.println(max);
  }

  public static int digitSum(String n)
  {
    char[] digit = n.toCharArray();
    int sum = 0;
    for(int i = 0; i < digit.length; i++)
    {
      sum += ((int)digit[i] - 48); //48 is ASCII value for '0'
    }
    return sum;
  }
}