# Project Euler #119 – Java

You can see the problem here: Problem #119.

I brute-forced the problem, and my code is very ugly. It contains a loop that search for *a*s, and the loop is pretty much infinite because of the large numbers involve. My code only print out possible *a*_{30}, so you also need to try the numbers to find the real solution (luckily, for 30, it gives out the solution right away). For large number, my code fails miserably, but it can cope with a small number like 30. I solved the question, so whatever.

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; } }

Runs in <1 millisecond on my computer. The <1 millisecond is the time it took for the answer to be found and printed, and does not involve the huge long (basically infinite) loop. My solution is such a failure, sigh, CU

## Leave a Reply