From 1 to Infinity

We need the sum of digits in

$123456789101112131415\ldots$

cut after exactly $k$ digits.

The main trap is thinking about the sequence as a string. That string has length $10^{15}$ in the biggest case, so yeah, that plan gets nuked from orbit. Work with blocks instead.

Block Structure

Group numbers by digit length:

• $1$-digit numbers: $1,2,\ldots,9$
• $2$-digit numbers: $10,11,\ldots,99$
• $3$-digit numbers: $100,101,\ldots,999$

For length $d$:

• first number is $10^{d-1}$
• count of numbers is $9\cdot 10^{d-1}$
• total digits in this whole block is

$d\cdot 9\cdot 10^{d-1}$

So we can repeatedly remove whole blocks from $k$.

When we remove a whole block, we also add the sum of digits of all numbers in that block.

Eventually, $k$ lands inside one specific block of $d$-digit numbers.

What Happens Inside The Final Block

Suppose after removing earlier blocks, we are inside the $d$-digit block.

Let

$start = 10^{d-1}$

The remaining prefix includes:

$q = \left\lfloor \frac{k}{d}\right\rfloor$

complete numbers, namely

$start, start+1, \ldots, start+q-1$

and then

$r = k \bmod d$

digits from the next number:

$start+q$

So the answer is:

1. digit sums of all fully removed blocks,
2. plus digit sums of numbers $start$ through $start+q-1$,
3. plus the first $r$ digits of $start+q$.

That reduces the problem to one helper: quickly compute the sum of digits from $1$ to $n$.

Digit Sum From $1$ To $n$

Let $F(n)$ be the sum of all digits appearing in all numbers from $1$ to $n$.

We compute contribution independently for every decimal place $p = 1,10,100,\ldots$.

For a fixed place $p$, split $n$ like this:

$$high = \left\lfloor \frac{n}{10p} \right\rfloor$$ $$cur = \left\lfloor \frac{n}{p} \right\rfloor \bmod 10$$ $$low = n \bmod p$$

Now count the contribution of this digit position.

Every full cycle of length $10p$ contains each digit $0,1,\ldots,9$ exactly $p$ times at this position. The sum per full cycle is:

$45p$

There are high full cycles, so that gives:

$45\cdot high\cdot p$

Then comes the partial cycle.

Digits smaller than cur have already appeared for a full run of length $p$ each:

$0 + 1 + \cdots + (cur-1) = \frac{cur(cur-1)}2$

so they contribute:

$\frac{cur(cur-1)}2\cdot p$

Finally, digit cur appears for the last $low+1$ numbers, contributing:

$cur\cdot(low+1)$

So this position contributes:

$45\cdot high\cdot p + \frac{cur(cur-1)}2\cdot p + cur\cdot(low+1)$

Sum that over all powers of $10$, and we get $F(n)$.

Then the sum of digits from $L$ to $R$ is just:

$F(R)-F(L-1)$

Putting It Together

For each test case:

1. Start with $d=1$.
2. While the whole $d$-digit block fits inside the remaining $k$ digits:
   • add digit sum of all numbers in that block,
   • subtract the block length from $k$,
   • move to the next digit length.
3. Now $k$ lies inside the current block.
4. Add the digit sum of the $q=k/d$ complete numbers.
5. Add the first $r=k\bmod d$ digits of the next number.

The largest $k$ is only $10^{15}$, so there are fewer than $20$ digit lengths. Each call to $F(n)$ also checks fewer than $20$ decimal positions. Tiny.

Complexity

Per test case:

$O(\log k)$

Memory:

$O(1)$