Detailed mathematical approach

Problem Summary

For each integer \(x\) with \(0 \le x < 10^n\), write \(x\) as an \(n\)-digit decimal string by allowing leading zeros. Sort those \(n\) digits into nondecreasing order, then read the result as an ordinary base-10 integer, so any leading zeros disappear automatically. The task is to compute the total of these sorted values for \(n=18\), modulo \(1123455689\).

A naive computation would examine all \(10^{18}\) inputs. The key observation is that the sorted result depends only on how many times each digit appears, not on the original order of the digits.

Mathematical Approach

Let \(S(n)\) be the required sum over all \(n\)-digit strings with leading zeros allowed.

Step 1: Replace each number by its digit counts

For one decimal string, let \(c_d\) be the number of occurrences of digit \(d\), where \(d \in \{0,1,\dots,9\}\). Then

$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$

Once these counts are known, the sorted image of the number is fixed. Therefore we can sum by digit-multiplicity vectors instead of by individual numbers.

The implementations iterate over \(c_1,\dots,c_9\) and infer the zero count from

$c_0=n-\sum_{d=1}^9 c_d.$

This is enough because zeros contribute to the multiplicity of the multiset, but after sorting they only create leading zeros, which do not affect the final integer value.

Step 2: Write the sorted value in closed form

Define the repunit of length \(k\) by

$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$

If digit \(d\) appears \(c_d\) times, then its block in the sorted number contributes \(dR_{c_d}\). That block must then be shifted left by the number of digits that appear to its right, namely

$t_d=\sum_{j=d+1}^9 c_j.$

So the sorted value attached to the count vector is

$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$

This formula automatically ignores the leading zero block. It is equivalent to appending digit blocks one by one in increasing order, using the recurrence

$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c.$

Step 3: Count how many original strings share those counts

For a fixed digit multiset \((c_0,\dots,c_9)\), the number of different original strings is the multinomial coefficient

$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$

Since the search chooses only the nonzero counts explicitly, it is convenient to write

$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s,$

and therefore

$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$

This weight counts all permutations of the multiset, including those that begin with zero. That is correct, because the original problem ranges over all integers from \(0\) to \(10^n-1\), equivalently over all \(n\)-digit strings with leading zeros allowed.

Step 4: Sum over all multiplicity vectors

Combining the sorted value with its multiplicity gives

$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$

The final answer required by the problem is

$S(18)\bmod 1123455689.$

This formula matches the exact combinatorial structure used by the implementations: one term for each admissible vector of digit counts, no term for the astronomically many raw input strings.

Step 5: Worked Example for \(n=2\)

For \(n=2\), the method groups the \(100\) strings from \(00\) to \(99\) by their digit multisets.

If the digits are \(\{0,d\}\) with \(1\le d\le 9\), the sorted value is \(d\), and there are \(2\) original strings: \(0d\) and \(d0\).

If the digits are \(\{d,d\}\) with \(1\le d\le 9\), the sorted value is \(11d\), and there is \(1\) original string.

If the digits are \(\{a,b\}\) with \(1\le a<b\le 9\), the sorted value is \(10a+b\), and there are \(2\) original strings.

Hence

$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$

Evaluating the three parts gives

$S(2)=90+495+2880=3465.$

As a local multiset example, counts \((c_0,c_1,c_3)=(1,2,1)\) correspond to the sorted value \(113\), and the multiplicity is \(4!/(1!\,2!\,1!)=12\), so that single multiset contributes \(1356\).

How the Code Works

The C++, Python, and Java implementations precompute three short tables up to \(n\): factorials, powers of \(10\) modulo the target modulus, and repunits modulo the same modulus. Because \(n=18\), the exact factorial values still fit comfortably in 64-bit arithmetic, so the multinomial weights can be formed exactly before the final modular reduction.

After that, the implementation performs a depth-first search over digits \(1\) through \(9\). At each step it chooses how many copies of the current digit to use, updates the product of factorial denominators, and appends the new repeated-digit block to the current sorted value with

$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c \pmod{1123455689}.$

When the search reaches digit \(9\), the remaining unused positions are exactly the zeros. The implementation then computes the multinomial multiplicity, multiplies it by the accumulated sorted value, and adds the result to the answer modulo \(1123455689\).

Complexity Analysis

The search enumerates all nonnegative \(9\)-tuples \((c_1,\dots,c_9)\) with total at most \(n\). By stars and bars, the number of leaves is

$\binom{n+9}{9}.$

Each transition uses only constant-time arithmetic, so the total running time is \(O\!\left(\binom{n+9}{9}\right)\). The auxiliary tables use \(O(n)\) space, and the recursion depth is \(9\). For \(n=18\), this means \(\binom{27}{9}=4686825\) terminal multiplicity vectors, which is entirely manageable.

Footnotes and References

1. Problem page: Project Euler 885
2. Multinomial coefficients: Wikipedia - Multinomial theorem
3. Repunit numbers: Wikipedia - Repunit
4. Stars and bars counting: Wikipedia - Stars and bars
5. Digit multisets and permutations: Wikipedia - Multiset