Problem 159: Digital Root Sums of Factorisations

Mathematical Analysis

Digital root formula

The digital root has a well-known closed form:

for $n \ge 1$. Equivalently, $dr(n) = n \bmod 9$ if $n \not\equiv 0 \pmod{9}$, and $dr(n) = 9$ if $n \equiv 0 \pmod{9}$ (for $n > 0$).

Key property

For the digital root sum, note that $dr(a) + dr(b) \ge dr(ab)$ in general. This means splitting a factor into smaller factors can only maintain or increase the digital root sum.

Dynamic programming approach

We compute $\text{mdrs}(n)$ using a sieve-like approach:

Initialize $\text{mdrs}(n) = dr(n)$ for all $n$ (the trivial factorization with $n$ itself).

Then for each $a$ from 2 to $\sqrt{999999}$, for each multiple $n = a \cdot b$ where $b \ge a$:

This works because the optimal factorization of $n$ either has $n$ as a single factor (giving $dr(n)$), or splits as $n = a \cdot b$ for some $a \ge 2$, and we use the optimal factorization of $b$.

We iterate $a$ from 2 upward, and for each $a$, update all multiples. Since we process $a$ in increasing order and use the already-computed $\text{mdrs}(b)$ values, this correctly computes the maximum.

Correctness

If the optimal factorization of $n$ is $a_1 \le a_2 \le \cdots \le a_k$, then:

• The smallest factor is $a_1 \ge 2$.
• The remaining product is $b = n/a_1$ with $b \ge a_1$.
• $\text{mdrs}(n) = dr(a_1) + \text{mdrs}(b)$.

Since we iterate $a$ from 2 up and update $\text{mdrs}(n)$ to the maximum of its current value and $dr(a) + \text{mdrs}(n/a)$, we capture this optimal split.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

The sieve runs in $O(N \log N)$ time where $N = 999999$, since for each $a$, we process $O(N/a)$ multiples.

Answer

#include <bits/stdc++.h>
using namespace std;

const int LIMIT = 1000000;

int dr(int n) {
    if (n == 0) return 0;
    int r = n % 9;
    return r == 0 ? 9 : r;
}

int mdrs[LIMIT];

int main() {
    ios::sync_with_stdio(false);

    // Initialize mdrs[n] = dr(n)
    for (int n = 2; n < LIMIT; n++) {
        mdrs[n] = dr(n);
    }

    // Sieve: for each factor a >= 2, update multiples
    for (int a = 2; a * a < LIMIT; a++) {
        for (int j = a; (long long)a * j < LIMIT; j++) {
            int n = a * j;
            mdrs[n] = max(mdrs[n], dr(a) + mdrs[j]);
        }
    }

    long long total = 0;
    for (int n = 2; n < LIMIT; n++) {
        total += mdrs[n];
    }

    cout << total << endl;
    return 0;
}

LIMIT = 1000000

def dr(n):
    """Digital root of n."""
    if n == 0:
        return 0
    r = n % 9
    return 9 if r == 0 else r

# Initialize mdrs[n] = dr(n)
mdrs = [0] * LIMIT
for n in range(2, LIMIT):
    mdrs[n] = dr(n)

# Sieve: for each factor a >= 2, update all multiples a*j where j >= a
a = 2
while a * a < LIMIT:
    j = a
    while a * j < LIMIT:
        n = a * j
        val = dr(a) + mdrs[j]
        if val > mdrs[n]:
            mdrs[n] = val
        j += 1
    a += 1

total = sum(mdrs[2:])
print(total)