Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their sum back to $A$. Let $x_i$ be the element added on $i$-th iteration of the process. The question is: is there a simple formula describing $x_i$, or can they be computed faster than simulating the process? One can easily see that for $k = 2$ we have $x_i = 3i$, but no simple pattern is evident for $k > 2$.

UPD: thought I would add some actual numbers and observations.

Here's what happens for $k = 3$ (bold numbers are those not initially present in the set):

$x_1 = 1 + 2 + 3 = \mathbf{6}$

$x_2 = 4 + 5 + 6 = \mathbf{15}$

$x_3 = \mathbf{6} + 7 + 8 = \mathbf{21}$

$x_4 = 9 + 10 + 11 = \mathbf{30}$

$x_5 = 12 + 13 + 14 = \mathbf{39}$

$x_6 = 15 + \mathbf{15} + 16 = \mathbf{46}$

The sequence continues with $54, 62, 69, 78, 87, 93, 102, 111, 118, 126, 135, \ldots$

One observation is that extra numbers are far apart from each other, enough so that no two extra numbers end up in the same batch, hence each batch is either a run of $k$ consecutive numbers, or a run of $k - 1$ numbers with one extra.

If we look at consecutive differences $\Delta_i = x_{i + 1} - x_i$, we get a sequence $9, 6, 9, 9, 7, 8, 8, 7, 9, 9, 6, 9, 9, 7, 8, 9, 6, \ldots$ It looks like it can be split into triples with sum $24$ (implying $x_{3i + 1} = 6 + 24i$ for whatever reason?). Further update: a similar pattern seems to persist for any $k$: empirically $x_{ki + 1} = k(k + 1) / 2 + i(k^3 - k)$ for any integer $i \geq 0$.

Looking further down the sequence, there's a hint of periodicity which never seems to amount to much. *(Since this answer was becoming cluttered I've removed the huge table of differences, but one can probably find them in the edit history.)*

UPD: Bullet51 discovered what seems to be a complete solution for the case $k = 3$. Understanding how and why it works may be the key to cracking the general case as well.

UPD: Following in Bullet51's steps I decided to try my hand at constructing some finite state machines for larger $k$ (see their answer below for the legend). This resulted in pictures I feel painfully obliged to share.

$k = 4$:

[![k = 4][1]][1]

$k = 5$:

[![k = 5][2]][2]

$k = 6$:

[![k = 6][3]][3]

$k = 7$:

[![k = 7][4]][4]

I've verified all of these FSMs for the first $10^7$ differences in each case. Hopefully someone can make sense of what's going on here.

  [1]: https://i.sstatic.net/U1mPN.png
  [2]: https://i.sstatic.net/nH07G.png
  [3]: https://i.sstatic.net/MrnTu.png
  [4]: https://i.sstatic.net/jnQS7.png