Detailed mathematical approach

Problem Summary

Let \(D(n)\) denote the number of positive integers \(x<10^n\) whose usual decimal representation has a digit appearing in more than half of its positions. Such a digit is called dominating. The goal is to compute \(D(2022)\) modulo \(10^9+7\).

A direct scan over all numbers below \(10^{2022}\) is hopeless. The key simplification is to count valid numbers by decimal length and by the exact number of times the dominating digit appears.

Mathematical Approach

For each length \(\ell\), let \(A(\ell)\) be the number of dominating \(\ell\)-digit numbers. Then

$D(n)=\sum_{\ell=1}^{n} A(\ell).$

The remaining task is to derive a closed formula for \(A(\ell)\).

Step 1: Fix the length and the exact dominating multiplicity

Assume a length-\(\ell\) number has a dominating digit occurring exactly \(k\) times. By definition, domination means

$k>\frac{\ell}{2}.$

This strict inequality is important: two different digits cannot both appear more than half the time. So every dominating number has a unique dominating digit and contributes to exactly one value of \(k\).

Therefore, for fixed \(\ell\), the valid multiplicities are

$k=\left\lfloor\frac{\ell}{2}\right\rfloor+1,\ \left\lfloor\frac{\ell}{2}\right\rfloor+2,\ \dots,\ \ell.$

If \(N(\ell,k)\) denotes the number of \(\ell\)-digit numbers whose dominating digit appears exactly \(k\) times, then

$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell} N(\ell,k).$

Step 2: Choose the positions occupied by the dominating digit

Fix \(\ell\) and \(k\). First choose which \(k\) positions contain the dominating digit. There are

$\binom{\ell}{k}$

such position sets.

Once those positions are chosen, the remaining \(\ell-k\) positions must use digits different from the dominating digit. No extra condition is needed to stop another digit from also dominating, because the non-dominating positions are too few:

$\ell-k<k.$

So the combinatorics reduces to counting how many assignments are possible for one fixed choice of the \(k\) dominant positions.

Step 3: Handle the leading-digit restriction carefully

The first digit of an \(\ell\)-digit number cannot be \(0\), so the count is not just \(10\cdot 9^{\ell-k}\). The implementations implicitly resolve this by splitting into two cases for a fixed set of dominant positions.

If the first position is one of the \(k\) dominant positions, then the dominating digit itself must be nonzero. There are \(9\) choices for that digit, and every remaining non-dominant position has \(9\) choices because it may use any digit except the dominating one. This case contributes

$9\cdot 9^{\ell-k}=9^{\ell-k+1}.$

If the first position is not dominant, then the dominating digit may be zero or nonzero. Summing those possibilities gives

$9\cdot 8 + 1\cdot 9 = 81 = 9^2$

choices for the pair consisting of the dominating digit and the first digit: \(9\) nonzero dominant digits with \(8\) legal first digits each, or the dominant digit \(0\) with \(9\) legal first digits. The other \(\ell-k-1\) non-dominant positions again have \(9\) choices each, so this case contributes

$81\cdot 9^{\ell-k-1}=9^{\ell-k+1}.$

Both cases give the same value. That is why every chosen position set contributes exactly \(9^{\ell-k+1}\).

Step 4: Derive the closed count for one pair \((\ell,k)\)

Multiplying the number of position sets by the number of valid assignments for each set gives

$N(\ell,k)=\binom{\ell}{k}9^{\ell-k+1}.$

Hence the number of dominating numbers of length \(\ell\) is

$A(\ell)=\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}.$

Step 5: Sum over all decimal lengths

Adding the contributions of all lengths from \(1\) to \(n\) yields the final formula

$\boxed{D(n)=\sum_{\ell=1}^{n}\sum_{k=\lfloor \ell/2\rfloor+1}^{\ell}\binom{\ell}{k}9^{\ell-k+1}\pmod{10^9+7}.}$

This is the exact quantity accumulated by the C++, Python, and Java implementations.

Worked Example: \(D(4)=603\)

For \(n=4\), compute the contribution of each length separately.

For \(\ell=1\), only \(k=1\) is possible:

$\binom{1}{1}9^1=9.$

For \(\ell=2\), only \(k=2\) is allowed:

$\binom{2}{2}9^1=9.$

For \(\ell=3\), the allowed values are \(k=2\) and \(k=3\):

$\binom{3}{2}9^2+\binom{3}{3}9^1=3\cdot81+9=252.$

For \(\ell=4\), the allowed values are \(k=3\) and \(k=4\):

$\binom{4}{3}9^2+\binom{4}{4}9^1=4\cdot81+9=333.$

Therefore

$D(4)=9+9+252+333=603,$

which matches the small checkpoint used by the implementations.

How the Code Works

The implementations all follow the same numerical strategy. They precompute factorials, inverse factorials, and powers of \(9\) up to the requested limit \(n\). Because the modulus

$M=10^9+7$

is prime, inverse factorials can be obtained using Fermat's little theorem:

$a^{M-1}\equiv 1 \pmod{M}\qquad\Longrightarrow\qquad a^{-1}\equiv a^{M-2}\pmod{M}.$

After that precomputation, every binomial coefficient \(\binom{\ell}{k}\) is available in constant time. The implementation then loops over all lengths \(\ell=1,\dots,n\), loops over all valid dominating multiplicities \(k>\ell/2\), evaluates the term \(\binom{\ell}{k}9^{\ell-k+1}\) modulo \(M\), and accumulates the result.

Complexity Analysis

Building the factorial, inverse-factorial, and power tables costs \(O(n)\) time and \(O(n)\) memory. The main computation is a double sum over all pairs \((\ell,k)\) with \(1\le \ell\le n\) and \(k>\ell/2\), which performs

$\sum_{\ell=1}^{n}\left(\ell-\left\lfloor\frac{\ell}{2}\right\rfloor\right)=O(n^2)$

constant-time updates. Therefore the total running time is \(O(n^2)\) and the memory usage is \(O(n)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=788
2. Binomial coefficient: Wikipedia - Binomial coefficient
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Fermat's little theorem: Wikipedia - Fermat's little theorem
5. Binomial coefficients modulo a prime: cp-algorithms - Binomial coefficients