### Digital root sums of factorisations题号：159 难度： 60 中英对照

Digital root sums of factorisations

A composite number can be factored many different ways. For instance, not including multiplication by one, 24 can be factored in 7 distinct ways:

24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24

Recall that the digital root of a number, in base 10, is found by adding together the digits of that number, and repeating that process until a number is arrived at that is less than 10. Thus the digital root of 467 is 8.

We shall call a Digital Root Sum (DRS) the sum of the digital roots of the individual factors of our number.
The chart below demonstrates all of the DRS values for 24.

Factorisation Digital Root Sum
2x2x2x3 9
2x3x4 9
2x2x6 10
4x6 10
3x8 11
2x12 5
24 6

The maximum Digital Root Sum of 24 is 11.
The function mdrs(n) gives the maximum Digital Root Sum of n. So mdrs(24)=11.
Find ∑mdrs(n) for 1 < n < 1,000,000.

24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24

2x2x2x3 9
2x3x4 9
2x2x6 10
4x6 10
3x8 11
2x12 5
24 6

### Code

public final class p159 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public String run() {
int[] X = new int[1000000];
int sum = 0;
for (int i = 2; i < X.length; i++)
X[i] = (i - 1) % 9 + 1;
for (int j = 2; j < 1000000; j++) {
int drsj = X[j];
for (int k = 2, n = j + j; k <= j && n < 1000000; k++, n += j)
X[n] = Math.max(X[n], drsj + X[k]);
sum += drsj;
}
return sum+"";
}

}
14489159
107ms