Project Euler

Total Inversion Count of Digit Strings

For a digit string d_1 d_2... d_n with digits in {0, 1,..., 9}, the inversion count is #{(i,j): 1 <= i < j <= n, d_i > d_j}. Let T(n) be the sum of inversion counts over all 10^n digit strings of l...

Source sync Apr 19, 2026

Problem #0705

Level Level 22

Solved By 548

Languages C++, Python

Answer 480440153

Length 185 words

modular_arithmeticnumber_theoryarithmetic

The inversion count of a sequence of digits is the smallest number of adjacent pairs that must be swapped to sort the sequence.

For example, $34214$ has inversion count of $5$: $34214 \to 32414 \to 23414 \to 23144 \to 21344 \to12344$.

If each digit of a sequence is replaced by one of its divisors a divided sequence is obtained.

For example, the sequence $332$ has $8$ divided sequences: $\{332,331,312,311,132,131,112,111\}$.

Define $G(N)$ to be the concatenation of all primes less than $N$, ignoring any zero digit.

For example, $G(20) = 235711131719$.

Define $F(N)$ to be the sum of the inversion count for all possible divided sequences from the master sequence $G(N)$.

You are given $F(20) = 3312$ and $F(50) = 338079744$.

Problem 705: Total Inversion Count of Digit Strings

Mathematical Foundation

Theorem 1 (Total Inversion Formula). For all $n \ge 2$ ,

T(n) = \frac{45\, n(n-1)}{2} \cdot 10^{n-2}.

Proof. We use linearity of summation. The total inversion count across all $10^n$ strings is

T(n) = \sum_{\text{all strings}} \sum_{\substack{i < j}} \mathbf{1}[d_i > d_j] = \sum_{1 \le i < j \le n} \sum_{\text{all strings}} \mathbf{1}[d_i > d_j].

For a fixed pair $(i, j)$ with $i < j$ , the inner sum counts the number of strings where $d_i > d_j$ . The digits $d_i$ and $d_j$ are chosen independently from $\{0, \ldots, 9\}$ , and the remaining $n - 2$ digits are free. The number of pairs $(a, b) \in \{0, \ldots, 9\}^2$ with $a > b$ is $\binom{10}{2} = 45$ . Therefore:

\sum_{\text{all strings}} \mathbf{1}[d_i > d_j] = 45 \cdot 10^{n-2}.

Summing over all $\binom{n}{2}$ position pairs:

T(n) = \binom{n}{2} \cdot 45 \cdot 10^{n-2} = \frac{45\,n(n-1)}{2} \cdot 10^{n-2}. \qquad\square

Lemma 1 (Modular Computation). To compute $T(10^{16}) \bmod p$ where $p = 10^9 + 7$ is prime, we evaluate:

T(10^{16}) \equiv 45 \cdot (10^{16}) \cdot (10^{16} - 1) \cdot 2^{-1} \cdot 10^{10^{16} - 2} \pmod{p}.

Proof. Direct substitution of $n = 10^{16}$ into the formula. The modular inverse $2^{-1} \bmod p$ exists since $\gcd(2, p) = 1$ , and is computed via Fermat’s little theorem as $2^{p-2} \bmod p$ . The term $10^{10^{16}-2} \bmod p$ is computed using Fermat’s little theorem: since $10^{p-1} \equiv 1 \pmod{p}$ , we reduce the exponent $10^{16} - 2$ modulo $p - 1$ . $\square$

Editorial

We compute n mod p, (n-1) mod p. We then since 10^{p-1} ≡ 1 (mod p), reduce exponent mod (p-1). Finally, combine: 45 * n * (n-1) / 2 * 10^{n-2}.

Pseudocode

p = 10^9 + 7 (prime)
Compute n mod p, (n-1) mod p
Compute 2^{-1} mod p via Fermat
Compute 10^{n-2} mod p
Since 10^{p-1} ≡ 1 (mod p), reduce exponent mod (p-1)
Combine: 45 * n * (n-1) / 2 * 10^{n-2}

Complexity Analysis

Time: $O(\log p)$ for modular exponentiation. All other operations are $O(1)$ .
Space: $O(1)$ .

Answer

\boxed{480440153}

C++ project_euler/problem_705/solution.cpp

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main() {
    long long n = 1e16;
    long long n_mod = n % MOD;
    long long nm1 = (n - 1) % MOD;
    long long inv2 = power(2, MOD - 2, MOD);
    long long p10 = power(10, n - 2, MOD);
    long long ans = 45 % MOD * n_mod % MOD;
    ans = ans * nm1 % MOD;
    ans = ans * inv2 % MOD;
    ans = ans * p10 % MOD;
    cout << ans << endl;
    return 0;
}

Python project_euler/problem_705/solution.py

"""
Problem 705: Total Inversion Count of Digit Strings
"""

def solve():
    MOD = 10**9 + 7
    n = 10**16
    # T(n) = 45 * n * (n-1) / 2 * 10^(n-2)
    n_mod = n % MOD
    nm1 = (n - 1) % MOD
    inv2 = pow(2, MOD - 2, MOD)
    power10 = pow(10, n - 2, MOD)
    result = 45 * n_mod % MOD * nm1 % MOD * inv2 % MOD * power10 % MOD
    return result

answer = solve()
print(answer)