Project Euler

Digital Root Patterns

Let d(n) denote the digital root of n (the single digit obtained by repeatedly summing digits). Define S(N) = sum_(k=1)^N k * d(k). Find S(10^6) mod 10^9+7.

Source sync Apr 19, 2026

Problem #0901

Level Level 22

Solved By 554

Languages C++, Python

Answer 2.364497769

Length 160 words

modular_arithmeticalgebrabrute_force

A driller drills for water. At each iteration the driller chooses a depth $d$ (a positive real number), drills to this depth and then checks if water was found. If so, the process terminates. Otherwise, a new depth is chosen and a new drilling starts from the ground level in a new location nearby.

Drilling to depth $d$ takes exactly $d$ hours. The groundwater depth is constant in the relevant area and its distribution is known to be an exponential random variable with expected value of $1$. In other words, the probability that the groundwater is deeper than $d$ is $e^{-d}$.

Assuming an optimal strategy, find the minimal expected drilling time in hours required to find water. Give your answer rounded to 9 places after the decimal point.

Problem 901: Digital Root Patterns

Mathematical Foundation

Theorem 1 (Digital Root Formula). For every positive integer $n$ ,

d(n) = 1 + \bigl((n-1) \bmod 9\bigr).

Proof. Write $n = 9q + r$ where $r \in \{0, 1, \ldots, 8\}$ . If $r \geq 1$ , then $n \equiv r \pmod{9}$ and $d(n) = r = 1 + (n - 1) \bmod 9$ . If $r = 0$ , then $n \equiv 0 \pmod{9}$ and $d(n) = 9$ , while $1 + (n-1) \bmod 9 = 1 + (9q - 1) \bmod 9 = 1 + 8 = 9$ . In both cases the formula holds. $\square$

Lemma 1 (Block Sum). For each integer $m \geq 0$ , the contribution of the block $\{9m+1, 9m+2, \ldots, 9m+9\}$ to $S$ is

B(m) = \sum_{j=1}^{9}(9m+j)\cdot j = 405m + 285.

Proof. Expand using Theorem 1:

B(m) = 9m\sum_{j=1}^{9} j + \sum_{j=1}^{9} j^2 = 9m \cdot 45 + 285 = 405m + 285,

where $\sum_{j=1}^{9} j = 45$ and $\sum_{j=1}^{9} j^2 = 285$ . $\square$

Theorem 2 (Closed-Form Evaluation). Let $N = 9q + r$ with $q = \lfloor N/9 \rfloor$ and $0 \leq r < 9$ . Then

S(N) = 405 \cdot \frac{q(q-1)}{2} + 285q + \sum_{j=1}^{r}(9q+j)\cdot j.

Proof. Partition $\{1, \ldots, N\}$ into $q$ complete blocks of 9 and a remainder of $r$ terms. By Lemma 1, the complete blocks contribute

\sum_{m=0}^{q-1} B(m) = \sum_{m=0}^{q-1}(405m + 285) = 405 \cdot \frac{q(q-1)}{2} + 285q.

The remainder block contributes $\sum_{j=1}^{r}(9q+j) \cdot j$ . Summing gives the result. $\square$

Corollary. For $N = 10^6$ : $q = 111111$ , $r = 1$ , and the remainder contributes $(9 \cdot 111111 + 1) \cdot 1 = 1000000$ . Hence

S(10^6) = 405 \cdot \frac{111111 \cdot 111110}{2} + 285 \cdot 111111 + 1000000 = 2499999166667.

Editorial

Let d(n) denote the digital root of n (the single digit obtained by repeatedly summing the digits of n). Define S(N) = sum_{k=1}^{N} k * d(k). Find S(10^6) mod 10^9 + 7.

Pseudocode

    q = N / 9 // integer division
    r = N mod 9
    total = 405 * q * (q - 1) / 2 + 285 * q
    For j from 1 to r:
        total += (9 * q + j) * j
    Return total mod (10^9 + 7)

Complexity Analysis

Time: $O(1)$ (the remainder loop runs at most 8 iterations).
Space: $O(1)$ .

Answer

\boxed{2.364497769}

C++ project_euler/problem_901/solution.cpp

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

int main() {
    long long N = 1000000;
    long long MOD = 1000000007;
    long long q = N / 9, r = N % 9;
    long long total = (405 % MOD) * ((q % MOD) * (((q - 1) % MOD + MOD) % MOD) % MOD) % MOD;
    total = (total * 500000004) % MOD; // modular inverse of 2
    total = (total + 285 % MOD * (q % MOD)) % MOD;
    for (int j = 1; j <= r; j++) {
        total = (total + (9 * q + j) % MOD * j) % MOD;
    }
    cout << total << endl;
    return 0;
}

Python project_euler/problem_901/solution.py

"""
Problem 901: Digital Root Patterns

Let d(n) denote the digital root of n (the single digit obtained by
repeatedly summing the digits of n). Define S(N) = sum_{k=1}^{N} k * d(k).
Find S(10^6) mod 10^9 + 7.

Key results:
    - Digital root: d(n) = 1 + (n-1) mod 9  for n >= 1
    - d(n) has period 9: pattern is 1,2,3,4,5,6,7,8,9,1,2,...
    - Each full block of 9 consecutive integers contributes a predictable sum
    - Closed-form via grouping into complete blocks of 9 + remainder

Methods:
    1. Closed-form via block decomposition (O(1) per block)
    2. Brute-force summation (verification)
    3. Incremental S(n) computation for visualization
"""

import numpy as np

def digital_root(n):
    """Digital root of n using the modular formula."""
    if n == 0:
        return 0
    return 1 + (n - 1) % 9

def solve_closed(N=10**6):
    """
    Closed-form computation of S(N) = sum(k * d(k) for k=1..N) mod 10^9+7.

    Group k=1..N into complete blocks of 9 consecutive integers.
    Block i (0-indexed) covers k = 9i+1 .. 9i+9.
    Within block i, for j=1..9: k = 9i+j, d(k) = j.
    Contribution = sum_{j=1}^{9} (9i+j)*j = 9i*45 + sum(j^2,j=1..9)
                 = 405i + 285.
    Sum over q complete blocks: 405*q*(q-1)/2 + 285*q.
    Then handle the partial remainder block.
    """
    MOD = 10**9 + 7
    q, r = divmod(N, 9)
    total = 405 * q * (q - 1) // 2 + 285 * q
    # Remainder: k = 9q+j for j=1..r
    for j in range(1, r + 1):
        total += (9 * q + j) * j
    return total % MOD

def solve_brute(N):
    """Brute force S(N) = sum(k * d(k) for k=1..N). For verification only."""
    return sum(k * digital_root(k) for k in range(1, N + 1))

def cumulative_s(N):
    """Return array where result[i] = S(i) for i=0..N."""
    s = np.zeros(N + 1, dtype=np.int64)
    for k in range(1, N + 1):
        s[k] = s[k - 1] + k * digital_root(k)
    return s

# Verification
for test_n in [27, 100, 1000]:
    assert solve_closed(test_n) == solve_brute(test_n), f"Mismatch at N={test_n}"

# Known: S(9) = 1*1+2*2+3*3+4*4+5*5+6*6+7*7+8*8+9*9 = 285
assert solve_closed(9) == 285
assert solve_closed(18) == 285 + (10*1+11*2+12*3+13*4+14*5+15*6+16*7+17*8+18*9)

# Solve
answer = solve_closed()
print(answer)