Detailed mathematical approach

Problem Summary

For each pair \((s,m)\), let \(f(s,m)\) be the \(m\)-th positive integer whose decimal digits sum to \(s\), with numbers ordered in the usual increasing order. The target quantity is

$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$

For the full input range, both the digit sums and the occurrence ranks are far too large for brute force. The solution therefore counts how many admissible numbers lie in each length block, identifies the block containing the required rank, and then reconstructs the number digit by digit.

Mathematical Approach

The key simplification is to replace each digit by its deficit from \(9\). That turns the digit-sum constraint into a bounded composition problem, which can be counted exactly with inclusion-exclusion.

Step 1: Turn the digit-sum condition into a bounded composition

Suppose an \(\ell\)-digit number has decimal digits \(a_1,\dots,a_\ell\). Define deficits

$b_i=9-a_i.$

Then every \(b_i\) lies in \(\{0,\dots,9\}\), and

$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$

The first digit cannot be zero, so \(a_1\ge 1\), which means

$b_1\in\{0,\dots,8\}.$

All remaining deficits may still range from \(0\) to \(9\). Therefore an \(\ell\)-digit number with digit sum \(s\) is equivalent to choosing \(b_1,\dots,b_\ell\) with one slightly tighter bound on the first coordinate.

The smallest feasible length is

$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$

because even the largest possible \(\ell\)-digit number contributes only \(9\ell\) to the digit sum.

Step 2: Count bounded suffixes by inclusion-exclusion

Let \(A(d,t)\) denote the number of length-\(d\) strings over \(\{0,\dots,9\}\) whose digits sum to \(t\). Without the upper bound \(9\), stars and bars gives \(\binom{d+t-1}{t}\). To enforce the upper bound, subtract cases where one or more coordinates are at least \(10\). The resulting exact formula is

$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$

This is the counting engine used throughout the algorithm. The values can be enormous, so the implementation evaluates them with arbitrary-precision integers instead of reducing them modulo \(10^9+7\).

Step 3: Count numbers of a fixed length

Let \(C_\ell(s)\) be the number of positive \(\ell\)-digit integers whose digit sum is \(s\). Once the first deficit \(b_1\) is chosen, the remaining \(\ell-1\) positions form an unrestricted bounded composition. Hence

$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$

Numbers with fewer digits are always smaller than numbers with more digits, so the desired occurrence rank \(m\) lies in the first length \(\ell\) satisfying

$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$

After that, the rank inside the chosen block is simply \(m\) minus the total contribution of all shorter lengths.

Step 4: Unrank inside the chosen length

Now suppose \(r\) positions remain to be filled and the remaining deficit to distribute is \(D\). If the next digit has deficit \(b\), then the number of valid completions is

$A(r-1,D-b).$

To preserve increasing numeric order, candidate digits are tested from smallest to largest. In terms of deficits, that means testing from largest to smallest. Whenever the target rank exceeds the size of a whole block, that block is skipped and its size is subtracted from the rank. The first block not skipped determines the next digit.

If \(D=0\), all remaining digits must be \(9\). More generally, the lexicographically last block is the block beginning with a run of \(9\)s. If \(q\) leading \(9\)s are fixed while \(r\) positions remain, then the surviving suffix count is

$A(r-q,D),$

so the number of admissible suffixes that come before that block is

$A(r,D)-A(r-q,D).$

This monotone quantity is why the implementation can binary-search the length of a leading run of \(9\)s and append that run in one jump.

Worked Example: \(f(10,10)=109\)

The smallest feasible length is \(\lceil 10/9\rceil=2\). The two-digit numbers with digit sum \(10\) are

$19,28,37,46,55,64,73,82,91,$

so \(C_2(10)=9\). Therefore the 10th occurrence does not lie in the two-digit block; it is the first element of the three-digit block.

For \(\ell=3\), the deficit is

$\Delta=27-10=17.$

Trying first digit \(1\) means first deficit \(8\), leaving deficit \(9\) across the last two digits. The number of completions is

$A(2,9)=10,$

so rank \(1\) already lies in that first block. Thus the leading digit is \(1\). Among the remaining two-digit suffixes with digit sum \(9\), the smallest is \(09\), so the first three-digit number with total digit sum \(10\) is \(109\). Hence

$f(10,10)=109.$

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. First, they evaluate exact combinatorial counts for bounded digit sums using arbitrary-precision integers, because the intermediate ranks are much larger than machine integers. Second, they accumulate length counts until the target occurrence rank enters one specific length block. Third, they reconstruct the required number digit by digit by repeatedly asking how many completions each candidate next digit allows.

The number itself is never materialized as a gigantic decimal integer. Instead, the implementation keeps the constructed value modulo \(10^9+7\) and updates it through the recurrence \(x\mapsto 10x+d\). When an entire run of \(9\)s is known at once, it appends that run with

$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}.$

Finally, the outer summation evaluates the procedure for each \(n\) with \(s=n^3\) and occurrence rank \(n^4\). The C++ implementation optionally partitions that outer loop across threads, while the Python and Java implementations use the same logic serially.

Complexity Analysis

For one query \(f(s,m)\), suppose the selected number has length \(\ell\). The length-location phase evaluates \(C_t(s)\) for consecutive lengths \(t\) from \(\lceil s/9\rceil\) up to \(\ell\). The unranking phase performs \(O(\ell)\) digit decisions, with a constant number of bounded-composition counts at each step and an occasional \(O(\log \ell)\) binary search when jumping across a run of \(9\)s.

The dominant arithmetic cost comes from the inclusion-exclusion formula for \(A(d,t)\), which contains \(O(\lfloor t/10\rfloor+1)\) terms and uses big-integer binomial coefficients. Memory usage is modest: apart from the big integers storing counts and ranks, only a small amount of state is maintained. In practice this is fast enough for the full sum up to \(k=10^4\), especially when the outer loop is parallelized.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=685
2. Digit sum: Wikipedia - Digit sum
3. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
4. Stars and bars: Wikipedia - Stars and bars
5. Lexicographic order: Wikipedia - Lexicographic order