Project Euler #119 Make Faster
- by gangqinlaohu
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
