Project Euler/56

Problem Statement

Given numbers of the form $ a^b $, where a, b <= 100, we are asked to find the values of a and b with the maximum digital sum.

Link: https://projecteuler.net/problem=56

Solution Technique

The key to this problem is to do a bit of back-of-the-envelope estimation. We have about 100 x 100 = 10,000 numbers to explore, and each one will result in a number up to $ 100^{100} $, or 101 digits.

The computer will only be doing multiplication, so this task can actually be done in a reasonable amount of time.

Code

Driver:

		int maxSum = 0;
		int maxA = 0;
		int maxB = 0;
		for(int a=1; a<100; a++) {
			for(int b=1; b<100; b++) { 
				BigInteger x = new BigInteger( Integer.toString(a) );
				x = x.pow(b);
				int sum = computeDigitalSum(x);
				if(sum>maxSum) {
					maxSum = sum; maxA = a; maxB = b;
				}
			}
		}
		System.out.println(maxSum);

The utility method to compute the digital sum:

	public static int computeDigitalSum(BigInteger n) { 
		char[] s = n.toString().toCharArray();
		int runningSum = 0;
		for(int i=0; i<s.length; i++) {
			int digit = Character.digit(s[i],10);
			runningSum += digit;
		}
		return runningSum;
	}

Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/056/BigNums.java