Project Euler #119 Make Faster

Question

Trying to solve Project Euler problem 119:

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 8^3 = 512. Another example of a number with this property is 614656 = 28^4.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

Question: Is there a more efficient way to find the answer than just checking every number until a30 is found?

---

My Code

    int currentNum = 0;
    long value = 0;
    for (long a = 11; currentNum != 30; a++){ //maybe a++ is inefficient
        int test = Util.sumDigits(a);
        if (isPower(a, test)) {
            currentNum++;
            value = a;
            System.out.println(value + ":" + currentNum);
        }
    }
    System.out.println(value);

isPower checks if a is a power of test. Util.sumDigits:

    public static int sumDigits(long n){
        int sum = 0;
        String s = "" + n;
        while (!s.equals("")){
            sum += Integer.parseInt("" + s.charAt(0));
            s = s.substring(1);
        }
        return sum;
    }

program has been running for about 30 minutes (might be overflow on the long). Output (so far):

81:1

512:2

2401:3

4913:4

5832:5

17576:6

19683:7

234256:8

390625:9

614656:10

1679616:11

17210368:12

34012224:13

52521875:14

60466176:15

205962976:16

612220032:17

Answer 1

The solution is a 15 digit number. Good luck optimising the summing enough to make that run fast enough to check every single number.

Turn the problem on its head. The sum of digits is a relatively low number (maximum of 9 x number of digits in the number), and the powers will also be relatively low (it doesn't take a large power to raise even a small number to be 15 digits).

So loop over the sums and powers, calculate the total (you can keep a running total in the inner loop with a multiply, not even a power calc needed) and then sum the digits of that to see if it matches your loop variable.

The numbers won't be in order, so calculate more than you need and sort the results.

Should run in about a second.