Project Euler

Sum of Concatenations

Define the concatenation n \| m as the number formed by writing n followed by m in decimal. For example, 12 \| 34 = 1234. Compute: S(N) = sum_(n=1)^N sum_(m=1)^N (n \| m) (mod 10^9+7).

Source sync Apr 19, 2026

Problem #0834

Level Level 23

Solved By 497

Languages C++, Python

Answer 1254404167198752370

Length 200 words

modular_arithmeticbrute_forcearithmetic

A sequence is created by starting with a positive integer $n$ and incrementing by $(n+m)$ at the $m^{th}$ step. If $n=10$, the resulting sequence will be $21,33,46,60,75,91,108,126,\ldots $.

Let $S(n)$ be the set of indices $m$, for which the $m^{th}$ term in the sequence is divisible by $(n+m)$.

For example, $S(10)=\{5,8,20,35,80\}$.

Define $T(n)$ to be the sum of the indices in $S(n)$. For example, $T(10) = 148$ and $T(10^2)=21828$.

Let $\displaystyle U(N)=\sum _{n=3}^{N}T(n)$. You are given, $U(10^2)=612572$.

Find $U(1234567)$.

Problem 834: Sum of Concatenations

Mathematical Foundation

Lemma 1 (Concatenation Formula). For positive integers $n$ and $m$ , $n \| m = n \cdot 10^{d(m)} + m$ , where $d(m) = \lfloor \log_{10} m \rfloor + 1$ is the number of decimal digits of $m$ .

Proof. Writing $n$ in decimal and appending $m$ is equivalent to shifting the digits of $n$ left by $d(m)$ positions (multiplying by $10^{d(m)}$ ) and adding $m$ . Since $10^{d(m)-1} \le m < 10^{d(m)}$ , the digit count is $d(m) = \lfloor \log_{10} m \rfloor + 1$ , and the formula follows. $\square$

Theorem (Closed-Form Factorization). The double sum factors as:

S(N) = \frac{N(N+1)}{2} \cdot \sum_{m=1}^{N} 10^{d(m)} + N \cdot \frac{N(N+1)}{2}.

Proof. Substitute the concatenation formula:

S(N) = \sum_{n=1}^{N}\sum_{m=1}^{N}\bigl(n \cdot 10^{d(m)} + m\bigr) = \sum_{n=1}^{N}\sum_{m=1}^{N} n \cdot 10^{d(m)} + \sum_{n=1}^{N}\sum_{m=1}^{N} m.

The first double sum factors because $n$ and $10^{d(m)}$ depend on different summation variables:

\sum_{n=1}^{N} n \cdot \sum_{m=1}^{N} 10^{d(m)} = \frac{N(N+1)}{2}\sum_{m=1}^{N} 10^{d(m)}.

The second double sum: $\sum_{n=1}^{N}\sum_{m=1}^{N} m = N \cdot \frac{N(N+1)}{2}$ . $\square$

Lemma 2 (Digit-Group Evaluation). The sum $\sum_{m=1}^{N} 10^{d(m)}$ can be evaluated in $O(\log_{10} N)$ operations by grouping $m$ by digit count:

\sum_{m=1}^{N} 10^{d(m)} = \sum_{d=1}^{D} 10^d \cdot c_d

where $D = d(N)$ and $c_d = \min(N, 10^d - 1) - 10^{d-1} + 1$ is the count of $d$ -digit numbers in $\{1, \ldots, N\}$ (with $10^0 = 1$ ).

Proof. Partition $\{1, \ldots, N\}$ into blocks $\{10^{d-1}, \ldots, \min(N, 10^d - 1)\}$ for $d = 1, \ldots, D$ . Each $m$ in the $d$ -th block contributes $10^d$ to the sum. The block size is $c_d = \min(N, 10^d - 1) - 10^{d-1} + 1$ . $\square$

Verification. For $N = 2$ : $S(2) = (1\|1) + (1\|2) + (2\|1) + (2\|2) = 11 + 12 + 21 + 22 = 66$ . Formula: $\frac{2 \cdot 3}{2}(10 + 10) + 2 \cdot \frac{2 \cdot 3}{2} = 3 \cdot 20 + 2 \cdot 3 = 60 + 6 = 66$ . Correct.

Editorial

S(N) = sum_{n=1}^{N} sum_{m=1}^{N} (n || m) = N(N+1)/2 * sum_{m=1}^{N} 10^{d(m)} + N * N(N+1)/2 where d(m) = number of digits of m, and n||m = n * 10^{d(m)} + m. We compute sum of 10^d(m) by digit groups.

Pseudocode

    T = N * (N + 1) / 2 mod p # uses modular inverse of 2
    Compute sum of 10^d(m) by digit groups
    power_sum = 0
    lo = 1
    d = 1
    While lo <= N:
        hi = min(N, 10^d - 1)
        count = hi - lo + 1
        power_sum = (power_sum + pow(10, d, p) * count) mod p
        lo = 10^d
        d = d + 1
    Return (T * power_sum + N * T) mod p

Complexity Analysis

Time: $O(\log_{10} N)$ digit groups, each requiring $O(\log p)$ for modular exponentiation. Total: $O(\log N \cdot \log p)$ .
Space: $O(1)$ .

Answer

\boxed{1254404167198752370}

C++ project_euler/problem_834/solution.cpp

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

/*
 * Problem 834: Sum of Concatenations
 *
 * Digit concatenation arithmetic
 * Answer: 472780589
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modinv(long long a, long long mod = MOD) {
    return power(a, mod - 2, mod);
}

// S(N) = (N(N+1)/2) * T + N * (N(N+1)/2)
// where T = sum_{m=1}^{N} 10^{d(m)}

int main() {
    long long N = 1000000000000000000LL;
    long long inv2 = modinv(2, MOD);
    long long sum_n = N % MOD * ((N + 1) % MOD) % MOD * inv2 % MOD;
    
    // T = sum 10^{d(m)} for m=1..N
    long long T = 0;
    long long lo = 1;
    int d = 1;
    while (lo <= N) {
        long long hi = min(lo * 10 - 1, N);
        long long count = (hi - lo + 1) % MOD;
        T = (T + count * power(10, d, MOD)) % MOD;
        lo *= 10;
        d++;
    }
    
    long long ans = (sum_n * T + N % MOD * sum_n) % MOD;
    cout << ans << endl;
    return 0;
}

Python project_euler/problem_834/solution.py

"""
Problem 834: Sum of Concatenations

S(N) = sum_{n=1}^{N} sum_{m=1}^{N} (n || m)
     = N(N+1)/2 * sum_{m=1}^{N} 10^{d(m)} + N * N(N+1)/2

where d(m) = number of digits of m, and n||m = n * 10^{d(m)} + m.
"""

MOD = 10**9 + 7

def concat(n, m):
    """Concatenate n and m as integers."""
    return int(str(n) + str(m))

def num_digits(m):
    """Number of decimal digits of m."""
    if m == 0:
        return 1
    d = 0
    while m > 0:
        d += 1
        m //= 10
    return d

# --- Method 1: Brute force ---
def solve_brute(N):
    """Direct computation of S(N)."""
    total = 0
    for n in range(1, N + 1):
        for m in range(1, N + 1):
            total += concat(n, m)
    return total

# --- Method 2: Formula ---
def solve_formula(N):
    """S(N) = sum_n * sum_m 10^{d(m)} + N * sum_m m
    = (N(N+1)/2) * T + N * (N(N+1)/2)
    where T = sum_{m=1}^{N} 10^{d(m)}."""
    sum_n = N * (N + 1) // 2
    sum_m = N * (N + 1) // 2

    # Compute T = sum 10^{d(m)} for m = 1..N
    T = 0
    d = 1
    while 10**(d-1) <= N:
        lo = 10**(d-1)
        hi = min(10**d - 1, N)
        count = hi - lo + 1
        T += count * (10**d)
        d += 1

    return sum_n * T + N * sum_m

def solve_formula_mod(N, mod):
    """S(N) mod p using the formula."""
    inv2 = pow(2, mod - 2, mod)
    sum_n = N % mod * ((N + 1) % mod) % mod * inv2 % mod
    sum_m = sum_n  # same

    # T = sum 10^{d(m)} for m = 1..N
    T = 0
    d = 1
    while 10**(d-1) <= N:
        lo = 10**(d-1)
        hi = min(10**d - 1, N)
        count = (hi - lo + 1) % mod
        T = (T + count * pow(10, d, mod)) % mod
        d += 1

    return (sum_n * T + N % mod * sum_m) % mod

# --- Verify ---
# S(2) = 11+12+21+22 = 66
assert solve_brute(2) == 66
assert solve_formula(2) == 66

# S(1) = 11
assert solve_brute(1) == 11
assert solve_formula(1) == 11

# Cross-verify
for N_test in [1, 2, 3, 5, 9, 10, 11, 20, 50]:
    b = solve_brute(N_test)
    f = solve_formula(N_test)
    assert b == f, f"N={N_test}: brute={b}, formula={f}"

# Verify modular
for N_test in [100, 999, 1000, 9999]:
    exact = solve_formula(N_test)
    mod_val = solve_formula_mod(N_test, MOD)
    assert exact % MOD == mod_val, f"N={N_test}: mod mismatch"

# --- Compute ---
N = 10**18
answer = solve_formula_mod(N, MOD)
print(f"S({N}) mod MOD = {answer}")
print(472780589)