Project Euler Problem 862

Solution

Answer: 6111397420935766740

Let the multiset of digits of a $k$-digit number $n$ be fixed. Suppose digit $d$ appears $c_d$ times, where

$$\sum_{d=0}^9 c_d = k.$$

We want to compute the contribution of all numbers with this digit multiset to $S(k)$.

1. Mathematical analysis

For a given multiset of digits, define:

$$P(c_0,\dots,c_9)$$

to be the number of valid $k$-digit integers that can be formed (no leading zero).

Step 1: Count valid permutations

Ignoring the leading-zero restriction, the number of distinct permutations is

$$\frac{k!}{\prod_{d=0}^9 c_d!}.$$

If $c_0>0$, some arrangements start with zero. Fix a zero in front and permute the remaining $k-1$ digits:

$$\frac{(k-1)!}{(c_0-1)!\prod_{d=1}^9 c_d!}.$$

Hence

$$P = \frac{k!}{\prod c_d!} - \frac{(k-1)!}{(c_0-1)!\prod_{d=1}^9 c_d!}.$$

Factorising gives

$$P = \frac{(k-c_0)(k-1)!}{\prod c_d!}.$$

Step 2: Sum $T(n)$ over one digit multiset

List all valid permutations in increasing order:

$$a_1 < a_2 < \cdots < a_P.$$

For the $i$-th number,

$$T(a_i)=P-i,$$

since exactly the later numbers are larger.

Therefore the total contribution of this multiset is

$$\sum_{i=1}^{P}(P-i) = 0+1+\cdots+(P-1) = \frac{P(P-1)}{2}.$$

Thus

$$S(k) = \sum_{\substack{c_0+\cdots+c_9=k\ c_d\ge 0}} \frac{P(P-1)}{2},$$

where

$$P = \frac{(k-c_0)(k-1)!}{\prod c_d!}.$$

The number of digit-count vectors is only

$$\binom{k+9}{9},$$

which for $k=12$ is

$$\binom{21}{9}=293930,$$

small enough to enumerate directly.

2. Python implementation

from math import factorial

def S(k):
    # Precompute factorials
    fact = [factorial(i) for i in range(k + 1)]

    counts = [0] * 10
    total = 0

    def dfs(digit, remaining):
        nonlocal total

        # Last digit count is forced
        if digit == 9:
            counts[9] = remaining

            # Compute denominator: product(c_i!)
            denom = 1
            for c in counts:
                denom *= fact[c]

            # Number of valid k-digit permutations
            P = (k - counts[0]) * fact[k - 1] // denom

            # Contribution of this multiset
            total += P * (P - 1) // 2
            return

        # Try all counts for this digit
        for c in range(remaining + 1):
            counts[digit] = c
            dfs(digit + 1, remaining - c)

    dfs(0, k)
    return total

# Check given example
print(S(3))   # 1701

# Required answer
print(S(12))

3. Code walkthrough

factorial(i) values are precomputed to avoid repeated work.
We recursively enumerate all digit-count vectors

$(c_0,\dots,c_9)$ with total $k$.

For each vector:
compute

$$\prod c_d!$$

evaluate

$$P = \frac{(k-c_0)(k-1)!}{\prod c_d!}$$

$$\frac{P(P-1)}{2}$$

to the total.

Verification

The program reproduces the given value:

$$S(3)=1701.$$

For the example $2302$:

digit counts: $c_0=1,c_2=2,c_3=1$
valid permutations:

$$P = \frac{(4-1)\cdot 3!}{1!,2!,1!} = 9$$

Thus the total contribution of this multiset is

$$\frac{9\cdot 8}{2}=36.$$

Indeed, the sorted list has ranks producing

$$8+7+\cdots+0=36.$$

Since $2302$ is the 5th item, $T(2302)=4$, matching the statement.

4. Final verification

The method exactly counts all $k$-digit numbers grouped by digit multiset.
Leading zeros are handled rigorously.
The sample $S(3)=1701$ matches perfectly.
Integer arithmetic only; no floating-point error.

Answer: 6111397420935766740