Detailed mathematical approach

Problem Summary

For each positive integer \(n\), let \(s(n)\) be the smallest positive integer whose decimal digit sum equals \(n\). Define

$S(k)=\sum_{n=1}^{k} s(n).$

The task is to evaluate

$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$

where \(F_0=0\), \(F_1=1\), and the remaining \(F_i\) are Fibonacci numbers. The key point is that \(F_{90}\) is far too large for any direct construction of all the numbers \(s(1),s(2),\dots,s(F_{90})\), so the solution must use a closed formula.

Mathematical Approach

The implementation uses two observations. First, the smallest number with a fixed digit sum has a very rigid decimal form. Second, once those values are grouped into blocks of nine, the cumulative sum becomes a short expression involving a power of \(10\).

Step 1: Find the exact form of \(s(n)\)

Write

$n=9a+b,\qquad 0\le b<9.$

Every decimal digit contributes at most \(9\), so the smallest possible number uses as few digits as possible. Among all numbers with that many digits, the smallest one places the largest digits at the far right and keeps the leftmost nonzero digit as small as possible. Therefore

$s(n)=(b+1)10^a-1.$

This is easy to visualize: if \(b>0\), the decimal expansion is the digit \(b\) followed by \(a\) copies of \(9\); if \(b=0\), the value is simply \(10^a-1\), namely \(a\) copies of \(9\).

Step 2: Sum one complete block of nine values

Now write

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

For a fixed \(a\ge 0\), the nine inputs \(9a+1,9a+2,\dots,9a+9\) contribute

$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$

The sum of that block is

$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$

So the first \(q\) complete blocks contribute

$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q.$

Step 3: Add the remaining tail

After the \(q\) full blocks, there are \(r\) extra terms:

$9q+1,9q+2,\dots,9q+r.$

Using the formula from Step 1, their contribution is

$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$

Since

$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2},$

the tail becomes

$\frac{r(r+3)}{2}10^q-r.$

Step 4: Combine both parts into a closed form for \(S(k)\)

Putting the block sum and the tail together gives

$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$

This is the central identity used by the implementations. Once \(10^q\) is known modulo \(10^9+7\), the whole value of \(S(k)\) follows from a constant number of modular additions and multiplications.

Worked Example: \(k=20\)

Here

$20=9\cdot 2+2,$

so \(q=2\) and \(r=2\). The single-value formula gives

$s(20)=(2+1)10^2-1=299.$

For the cumulative sum, substitute \(q=2\) and \(r=2\):

$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$

This is exactly the small checkpoint used before the full Fibonacci accumulation.

Step 5: Aggregate over the Fibonacci indices

The required answer is not a single \(S(k)\), but

$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$

So the algorithm generates Fibonacci numbers from \(F_0\) through \(F_{90}\), applies the closed form to each \(F_i\), and adds the results modulo \(10^9+7\). No huge decimal string for \(s(F_i)\) is ever constructed explicitly.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They first build the Fibonacci sequence up to index \(90\) using ordinary integer arithmetic. For each Fibonacci value \(k\), they split it into \(k=9q+r\), compute \(10^q \bmod 10^9+7\) by binary exponentiation, evaluate the closed form for \(S(k)\), normalize any intermediate subtraction back into the modular range, and add the result to the running total. The C++ implementation also performs a small exact sanity check at \(k=20\) to confirm that the closed form matches direct enumeration before processing the full sum.

Complexity Analysis

Evaluating one term \(S(k)\) requires one modular exponentiation, so the cost is \(O(\log q)=O(\log k)\). The outer sum has only \(89\) terms, from \(F_2\) through \(F_{90}\), so the total running time is

$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$

which is effectively constant for this input size. The implementations store \(91\) Fibonacci numbers and a few scalar values, so the memory usage is \(O(90)\), again effectively constant.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=684
2. Digit sum: Wikipedia - Digit sum
3. Fibonacci numbers: Wikipedia - Fibonacci number
4. Exponentiation by squaring: Wikipedia - Exponentiation by squaring
5. Modular arithmetic: Wikipedia - Modular arithmetic