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. Here are the first $999$ differences split into groups of $27$:
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 7 8 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 8 7 9 9 6 9 9 6 9 8 7 9
9 6 9 9 7 8 8 7 9 9 6 9 9 7 8 9 6 9 9 6 9 9 6 9 8 7 9
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.