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 = 5$:
$k = 6$:
$k = 7$:
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.
Best Answer
It seems that the sequence $Δ_i$ can be computed by a finite state machine for $k = 3$:
Instructions:
In order to compute $Δ_i$, let $S_n$ be the nth rightmost digit of the ternary expansion of $i$. Start from the vertex labelled $Start$. If there is a transition labelled $S_n$, make the transition. Otherwise, terminate at the current vertex, and $Δ_i$ is the label of the vertex.
Example: Compute $Δ_{24}$. As $24=(220)_3$, make the transitions $0$, $2$, $2$ and terminate at a vertex labelled $9$. So $Δ_{24}=9$.