Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  sum
Language: JAVA
Code:
final int TOLERABLE_LIMIT = 3; 
List<BigDecimal> a = new ArrayList<BigDecimal>();
int i = 7;
 
//loop - break condition at the beginning of loop
while (true) {
    i++;
 
    //break if i * i bigger than the current a[30] - meaning a[30] is for sure the answer
    //it takes so long for this condition to be fulfilled this is pretty much infinite
    if (a.size() >= 30 && a.get(29).compareTo(BigDecimal.valueOf(i * i)) < 0) {
        break;
    }
     
    //just slightly improve performace, and more importantly, take care of infinite loop involving 10, 100, 1000...
    int tempI = i;
    while (tempI % 10 == 0) tempI /= 10;
    if (tempI == 1) continue;
 
    //loop through the powers of current number, break out of loop if one of the following happens:
    //- if the digit sums exceed the current number three times in a row (a heuristic)
    //- if there is an a[30] and the current power exceeds it, no need to find a's that are bigger than a[30]
    BigDecimal number = BigDecimal.valueOf(tempI);
    BigDecimal currentPow = number.pow(2);
    int numOfFailures = 0;
    while (true) {
        currentPow = currentPow.multiply(number);
        int digitSum = digitSum(currentPow);
         
        if (digitSum == i) {
            if (!a.contains(currentPow)) a.add(currentPow);
            Collections.sort(a);
             
            if (a.size() >= 30) System.out.println(a.get(29));
        } else if (digitSum > i) {
            numOfFailures++;
            if (numOfFailures >= TOLERABLE_LIMIT) break;
        } else {
            numOfFailures = 0;
        }
 
        if (a.size() >= 30 && currentPow.compareTo(a.get(29)) > 0) break;
    }
}
Comments: