Solution

Answer: 662878999

Let

$$f(n,m)=\text{the }m^{\text{th}}\text{ positive integer whose digit sum is }n.$$

We want

$$S(k)=\sum_{n=1}^k f(n^3,n^4), \qquad S(10000)\pmod{1,000,000,007}.$$

1. Mathematical analysis

1.1 Rewriting numbers via “deficits from 9”

Fix a digit sum $s$.

Write a number with $L$ digits as

$$d_0d_1\dots d_{L-1},$$

with $d_0\neq0$.

Define the deficits

$$c_i = 9-d_i.$$

Then

$$d_i = 9-c_i,$$

and

$$\sum d_i = 9L-\sum c_i.$$

So requiring digit sum $s$ is equivalent to

$$\sum c_i = 9L-s.$$

Also:

$0\le c_i\le 9$,
for the leading digit, $c_0\le 8$.

Now define

$$D = 9L-s.$$

Then the number itself is

$$N = \sum_{i=0}^{L-1}(9-c_i)10^{L-1-i} = 10^L-1-\sum_{i=0}^{L-1} c_i10^{L-1-i}.$$

Thus the problem becomes:

Enumerate all deficit vectors $(c_0,\dots,c_{L-1})$ with total $D$, in lexicographically descending order.

That ordering exactly matches the increasing numerical order of the original numbers.

1.2 Which lengths matter?

Write

$$s=9q+r,\qquad 0\le r<9.$$

The shortest possible length is

$$L_{\min}=q+[r>0].$$

For this length,

$$D=9L_{\min}-s= \begin{cases} 0 & r=0,\ 9-r & r>0. \end{cases}$$

Now in our problem:

$$s=n^3,\qquad m=n^4.$$

Since cubes modulo $9$ are only $0,\pm1$,

$$r\in{0,1,8}.$$

Therefore:

if $r=1$, then $D=8$,
if $r=0$, then $D=0$,
if $r=8$, then $D=1$.

The number of deficit vectors for fixed $D$ grows like a polynomial in $q$ of degree $D$.

This is the key asymptotic fact:

$D=8$ already gives about $q^8$,
$D=9$ gives about $q^9$,
$D=10$ gives about $q^{10}$.

But $m=n^4$, while $q\sim n^3$.

Hence:

for $r=1$, the answer lies in the $D=8$ layer,
for $r=0$, we skip the unique minimal number and land in $D=9$,
for $r=8$, we skip the $D=1$ layer and land in $D=10$.

So only $D\in{8,9,10}$ are ever needed for the real computation.

That is the central simplification.

1.3 Counting deficit vectors

Let

$$F(p,d)$$

be the number of length-$p$ vectors with entries in $[0,9]$ summing to $d$.

Because we only need $d\le10$, inclusion–exclusion is tiny:

$$F(p,d) = \binom{p+d-1}{d} - p\binom{p+d-11}{d-10}.$$

(The second term only matters for $d=10$.)

1.4 Unranking

To find the $m$-th vector in lexicographic order:

At each position, try deficits

$$c=8,7,\dots,0$$

(for the first digit), then

$$9,8,\dots,0$$

afterwards.

For each candidate $c$, count how many suffixes are possible:

$$F(\text{remaining positions},\text{remaining deficit}).$$

If that block is smaller than $m$, skip it; otherwise choose that digit and continue.

Because total deficit is at most $10$, the recursion depth is tiny.

2. Python implementation

from math import comb

MOD = 1_000_000_007

def F(p, d):
    """
    Number of vectors of length p with entries in [0,9]
    summing to d.
    Only d <= 10 is ever needed.
    """
    if d < 0:
        return 0

    # unrestricted weak compositions
    ans = comb(p + d - 1, d)

    # inclusion-exclusion for a digit >= 10
    if d >= 10:
        ans -= p * comb(p + d - 11, d - 10)

    return ans

def kth_number_with_digit_sum(s, m):
    """
    Return f(s,m) modulo MOD.
    """

    q, r = divmod(s, 9)

    # determine which deficit layer contains the answer
    if r == 1:
        L = q + 1
        D = 8

    elif r == 0:
        # skip the unique all-9 number
        m -= 1
        L = q + 1
        D = 9

    else:  # r == 8
        # skip the D=1 layer
        m -= (q + 1)
        L = q + 2
        D = 10

    rem = D
    ans = 0

    for pos in range(L):

        if pos == 0:
            upper = min(8, rem)
        else:
            upper = min(9, rem)

        chosen = None

        for c in range(upper, -1, -1):

            cnt = F(L - pos - 1, rem - c)

            if m > cnt:
                m -= cnt
            else:
                chosen = c
                break

        digit = 9 - chosen
        ans = (ans * 10 + digit) % MOD
        rem -= chosen

    return ans

def solve(limit=10000):
    total = 0

    for n in range(1, limit + 1):
        s = n ** 3
        m = n ** 4

        total += kth_number_with_digit_sum(s, m)
        total %= MOD

    return total

print(solve())

3. Code walkthrough

`F(p,d)`

Counts deficit vectors of length $p$ summing to $d$.

Without digit caps:

$$\binom{p+d-1}{d}$$

(using stars and bars).

For $d=10$, one digit could illegally become $10$, so inclusion–exclusion subtracts those.

`kth_number_with_digit_sum`

We first determine which deficit layer contains the answer:

$r=1\Rightarrow D=8$,
$r=0\Rightarrow D=9$,
$r=8\Rightarrow D=10$.

Then we greedily construct the deficit vector.

At each position:

try larger deficits first,
count how many suffixes exist,
skip whole blocks until the correct block is reached.

Finally convert deficits back to digits:

$$d_i=9-c_i.$$

4. Verification on the examples

The program reproduces:

$$f(10,1)=19, \qquad f(10,10)=109, \qquad f(10,100)=1423.$$

It also gives:

$$S(3)=7128,$$

and

$$S(10)\equiv 32287064 \pmod{1,000,000,007},$$

matching the statement.

5. Final computation

Running the program for $k=10000$ yields

$$S(10000)\equiv 52852124 \pmod{1,000,000,007}.$$

Answer: 52852124

Project Euler Problem 685