A curious process with positive integers 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.
 A: To write the $k=3$ solution in closed form, we have
\begin{align*}
\Delta_n &= \sum_{i = 0}^{\lfloor \log_3 n\rfloor + 1} \delta_i(n),
\end{align*}
where, letting $n = (n_\ell \ldots {n_1})_3$ denote the ternary expansion of $n$, we define $\delta_i(n)$ for $i = 0, 1, 2$ to be
\begin{align*}
\delta_0(n) &= 9 \\
\delta_1(n) &= \begin{cases} -3 & \text{if } n \equiv 2 \pmod 3 \\
                          0 & \text{else} \end{cases} \\
\delta_2(n) &= \begin{cases} 1 & \text{if } n \equiv 12_3 \text{ or } 22_3\pmod9\\
                          -1 & \text{if } n \equiv 20_3 \text{ or } 21_3\pmod9\\
                          0 & \text{else} \end{cases}.
\end{align*}
Before we define $\delta_i$ in general, let
\begin{align*}
(12)_3^{(i)} :&= \sum_{\ell=0}^{i-1} 3^\ell + \sum_{\ell=0}^{\lfloor \frac{i-1}{2} \rfloor} 3^{2\ell} \\
(21)_3^{(i)} :&= \sum_{\ell=0}^{i-1} 3^\ell + \sum_{\ell=0}^{\lfloor \frac{i-1}{2} \rfloor} 3^{2\ell + 1}.
\end{align*}
Then $(12)_3^{(i)}$ has $i$-many ternary digits and is either of the form $12...12$ or $21....12$ depending on the parity of $i$ (e.g. $(12)_3^{(2)} = 12_3$ and $(12)_3^{(3)} = 212_3$). Similarly, $(21)_3^{(i)}$ has $i$-many ternary digits and is either of the form $21...21$ or $12...21$ depending on the parity of $i$.
Then define
\begin{align*}
\delta_i(n) &:= \begin{cases} (-1)^{i} & \text{if } n \equiv (21)_3^{(i)} \text{ or } 3^2(21)_3^{(i-2)} + 22_3\pmod {3^i}\\
                          (-1)^{i+1} & \text{if } n \equiv (12)_3^{(i)} \text{ or } 3^2(12)_3^{(i-2)} + 20_3 \pmod {3^i}\\
                          0 & \text{else} \end{cases} \\
\end{align*}
for all $i > 2$.

Observe that this is actually equivalent to the finite state machine given by Bullet51. Plus, this gives that $\Delta_{3n} + \Delta_{3n+1} + \Delta_{3n+2} = 24$ for any $n$ since $$\delta_i(3n) + \delta_{i}(3n+1) + \delta_{i}(3n+2) = \begin{cases}27 & \text{if } i=0 \\ -3 & \text{if } i=1 \\ 0 & \text{if } i > 1\end{cases}.$$ Similarly, we can express the other finite state machines for larger $k$ in terms of $\delta_i$ with conditions modulo $k^i$.
To explain such a formula, we can examine how the $x_n$ changes $\Delta_n$. Suppose $x_n$ appears in the expression for $x_{n'}$, i.e. $x_{n'} = a + b + c$ where $x_n$ is one of $a$, $b$, or $c$. Always writing $a \leq b \leq c$ and assigning the convention that $x_n = a$ if $a \neq b$, $x_n = b$ if $a=b$ and $x_n = c$ if $b=c$, then define
$$
y_n := \begin{cases} 0 & \text{if } x_n = a \\ 1 &\text{if } x_n = b \\ 2 &\text{if } x_n = c \end{cases}
$$
to be the position of $x_n$ in the expression of $x_{n'}$. Then observe that $x_{n'} \equiv y_n \pmod 3$. But also observe that $y_n$ depends on $\Delta_{n-1}$ modulo $3$:
$$
y_n = \begin{cases} y_{n-1} & \text{if } \Delta_{n-1} \equiv 2 \pmod 3 \\
              y_{n-1} + 1 & \text{if } \Delta_{n-1} \equiv 0 \pmod 3 \\
              y_{n-1} + 2 & \text{if } \Delta_{n-1} \equiv 1 \pmod 3 \end{cases}.
$$
If we chase through these modular relations, we can then build the expression for $\Delta_n$ that we have above as well as the finite state machines that have been given here. This is somewhat tricky but we can start with the fact that we expect $\Delta_n$ to be $9$ if $n+1$ and $n$ are not $m'$ for some $m$ (i.e. no other $x_m$ appears in their expression as the sum of three integers), we expect it to be $6$ if no $x_m$ appears in the expression for $x_n$ but does for $x_{n+1}$ with $y_m = 0$. Then we have these corrections $\delta_i = \pm 1$ (with $i > 1$) in the other cases.

While this should work for the analogous situations with other fixed $k$, the situation becomes more complicated for general $k$ and it is not immediately clear what a general formula would look like. However one can deduce the closed form for any $k$ by looking at the modular relation $x_{n’}$ and $y_n$ modulo $k$ and the relation between $y_n$ and $\Delta_{n-1}$ modulo $k$.
Also note that if we define $A$ using $\{m \in \mathbb{Z} \mid m > \ell \}$ with $\ell \geq 0$ instead of $\mathbb{N}$, we will get something extremely similar to this.
A: 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$.
