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:
\begin{align}
24 &= 2 \times 2 \times 2 \times 3\\
24 &= 2 \times 3 \times 4\\
24 &= 2 \times 2 \times 6\\
24 &= 4 \times 6\\
24 &= 3 \times 8\\
24 &= 2 \times 12\\
24 &= 24
\end{align}

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$.

FactorisationDigital Root Sum
$2 \times 2 \times 2 \times 3$$9$
$2 \times 3 \times 4$$9$
$2 \times 2 \times 6$$10$
$4 \times 6$$10$
$3 \times 8$$11$
$2 \times 12$$5$
$24$$6$

The maximum Digital Root Sum of $24$ is $11$.
The function $\operatorname{mdrs}(n)$ gives the maximum Digital Root Sum of $n$. So $\operatorname{mdrs}(24)=11$.
Find $\sum \operatorname{mdrs}(n)$ for $1 \lt n \lt 1\,000\,000$.

This is actually a problem from the Project Euler (Problem 159), so no created algorithm can solve all instances of the problem in reasonable time. But because you have specified a number, a highly optimized and specialized algorithm can work.

In the problem, you may tend to think that prime numbers would just return its digital root so you don’t need to calculate them. This thought leads us to consider the factor trees of the non-prime numbers. However, going through all combinations just to check which combination returns maximum digital root is an overkill and impractical.

Here’s a more optimized approach:

First, observe that we only need to worry about the final digital root of numbers because when we sum the digits over and over again, we should at last get a number from 1 to 9.

The digital root operation is basically finding the value of number modulo 9. For ancient Indians and Chinese, the congruence modulo 9 represents the essence of a number. Here are the properties of digital root (also known as Dr):

Dr(a+b) = Dr(Dr(a) + Dr(b))

Dr(a*b) = Dr(Dr(a) * Dr(b))

With these properties, it’s easy to see that the Dr is well-defined in addition and multiplication.

To get the maximum value of the digital root sum, we will build up the sequence step by step from lower numbers to higher numbers. For each number, we will check all possible divisors and take the one giving maximum digital root sum.

We first initialize mdrs[1] to 0. mdrs[n] generally denotes the maximum digital root sum for number n.

Then, for each number n from 2 to a million (not included), we do the following:

1. Initialize mdrs[n] as Dr(n). This handles the cases when n is prime.

2. Check each integer d from 2 up to sqrt(n). If d divides n, we calculate potential_mdrs = Dr(d) + mdrs[n/d]. We replace mdrs[n] with potential_mdrs if and only if potential_mdrs > mdrs[n].

Finally, we add up mdrs[n] for all n.

Note: Special attention needs to be paid to the cases when Dr(n) == 9, because for these cases, the digital root can’t be increased further.

Now, this algorithm is efficient and should finish within seconds.

The answer P(1000000) is 1259187438574927161.

Note: The problem is a programming one so it is meant to be solved by computer program, rather than manually. To derive the solution for such a large number, you will have to write a program in language of your choice using the outlined algorithm.

More Answers: