You can see the problem here: Problem #159.

This is my 100th question, woot! Now I just need to complete another 50 questions to become level 4. I doubt I can do another 20 questions, let alone 50, but I will try anyway. Now that little “celebration” is over with, let’s get back to the question. This question is pretty easy. The digital root of a number (in base 10) can be found using the following piecewise function (I love google):

$f(n) = \begin{cases} n\ (mod\ 9) & n\ (mod\ 9) \neq 0 \\ 9 & n\ (mod\ 9) = 0 \end{cases}$

In plain English, for any number n, find the remainder after dividing n by 9. The digital root of n will be the remainder, unless the remainder is 0, in which case the digital root is 9. Kudos for you if you know why this works (it’s not that hard, hint: it’s related to the fact if a number’s digit sum is divisible by 9, then the number itself is divisible by 9).

The maximal Digital Root Sum (MDRS) of each number can be found with dynamic programming since you can start with the MDRS of small numbers and use them to find the MDRS of the bigger numbers. For those of you who can’t google, dynamic programming involves solving complex problem by breaking it down into sub-problems (usually smaller version of the bigger problem) and doing those instead.

final int SIZE = 1000000;
int[] drs = new int[SIZE];
for (int i = 2; i < SIZE; i++) {
//prime number: mdrs = digital root
if (drs[i] == 0) {
drs[i] = i % 9;
if (drs[i] == 0) drs[i] = 9;
}
//a number's digital root can be its mdrs
else if (drs[i] < 10) {  //a single number's digital root cannot exceed 10
int candidate = i % 9;
if (candidate == 0) candidate = 9;
drs[i] = Math.max(drs[i], candidate);
}

int currentNum = i;
for (int factor = 2; factor <= i; factor++) {
currentNum += i;
if (currentNum >= SIZE) break;
drs[currentNum] = Math.max(drs[i] + drs[factor], drs[currentNum]);
}
}