Project Euler Problem 159

Solution

Answer: 14489159

Let $drs(n)$ denote the digital root of $n$.

A useful closed form is:

$$drs(n)= \begin{cases} 0 & n=0\ 1+((n-1)\bmod 9) & n>0 \end{cases}$$

So for all positive integers, $drs(n)\in{1,\dots,9}$, and:

• $drs(24)=2+4=6$
• $drs(467)=4+6+7=17\to1+7=8$

We define:

$$mdrs(n)=\max{\text{digital root sums over all factorizations of } n}$$

including the trivial factorization $n$ itself.

For example:

$$24 = 3\times 8$$

gives

$$drs(3)+drs(8)=3+8=11$$

and no factorization does better, so:

$$mdrs(24)=11$$

---

Key Insight

Suppose we split $n$ as:

$$n=d\cdot \frac{n}{d}$$

Then any optimal factorization of $n$ can be viewed as:

• choosing one divisor $d\ge2$,
• then optimally factorizing $n/d$.

Therefore:

$$mdrs(n)=\max\left(drs(n),\ \max_{d\mid n,\ 2\le d<n}\left(drs(d)+mdrs\left(\frac{n}{d}\right)\right)\right)$$

This is a classic dynamic programming / sieve recurrence.

Because every recursive term involves a smaller number $n/d < n$, we can compute values in increasing order.

---

Efficient Sieve Strategy

We need:

$$\sum_{n=2}^{999999} mdrs(n)$$

A naive factorization for every $n$ would be too slow.

Instead:

1. Precompute $drs(n)$ for all $n<10^6$.
2. Initialize:

$$mdrs(n)=drs(n)$$

1. For every divisor $d$, propagate updates to multiples:

If $n=d\cdot q$, then:

$$mdrs(n)\ge drs(d)+mdrs(q)$$

So:

for d in 2..N:
    for q in 2..N/d:
        n = d*q
        mdrs[n] = max(mdrs[n], drs[d] + mdrs[q])

This behaves like a divisor sieve and runs fast enough for $10^6$.

---

Python Implementation

LIMIT = 10**6

# ---------------------------------------------------------
# Compute digital roots
# drs(n) = 1 + ((n - 1) % 9) for n > 0
# ---------------------------------------------------------

drs = [0] * LIMIT

for n in range(1, LIMIT):
    drs[n] = 1 + (n - 1) % 9

# ---------------------------------------------------------
# Initialize mdrs with the trivial factorization: n itself
# ---------------------------------------------------------

mdrs = drs[:]

# ---------------------------------------------------------
# Dynamic programming sieve
#
# If n = d * q, then:
# mdrs[n] >= drs[d] + mdrs[q]
# ---------------------------------------------------------

for d in range(2, LIMIT):
    dd = drs[d]

    max_q = (LIMIT - 1) // d

    for q in range(2, max_q + 1):
        n = d * q

        candidate = dd + mdrs[q]

        if candidate > mdrs[n]:
            mdrs[n] = candidate

# ---------------------------------------------------------
# Sum all mdrs values for 2 <= n < 10^6
# ---------------------------------------------------------

answer = sum(mdrs[2:])

print(answer)

---

Code Walkthrough

Digital root table

drs[n] = 1 + (n - 1) % 9

This computes digital roots in constant time.

Examples:

• $drs(8)=8$
• $drs(24)=6$
• $drs(999)=9$

---

Initializing mdrs

mdrs = drs[:]

Every number has at least the trivial factorization:

$$n$$

so initially:

$$mdrs(n)\ge drs(n)$$

---

Divisor DP

For each divisor $d$, we iterate over all multiples:

n = d * q
candidate = drs[d] + mdrs[q]

This corresponds to taking:

$$n=d\times q$$

and using the best factorization of $q$.

Because $q<n$, its value is already known.

---

Verifying the Example $n=24$

The sieve eventually considers:

• $24=2\times12$
• $24=3\times8$
• $24=4\times6$

The best is:

$$drs(3)+mdrs(8)=3+8=11$$

So:

$$mdrs(24)=11$$

matching the problem statement.

---

Final Verification

The final sum should be:

• positive,
• on the order of $10^7$,
• since typical $mdrs(n)$ values are around 10–20 for numbers below $10^6$.

The computation gives:

$$14489159$$

which matches the known correct Project Euler result.

---

Answer: 14489159