42
$\begingroup$

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

$k = 5$:

k = 5

$k = 6$:

k = 6

$k = 7$:

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.

$\endgroup$
  • $\begingroup$ did you look for these sequences in the OEIS? $\endgroup$ – Noam D. Elkies Oct 13 '18 at 20:55
  • 5
    $\begingroup$ @NoamD.Elkies I sure did, but to no avail. $\endgroup$ – Mikhail Tikhomirov Oct 13 '18 at 20:56
  • 1
    $\begingroup$ The density of the largest difference in $\Delta_{k}$ (the largest difference is apparently $k^2$ for $k \geq 3$) seems to be monotonic increasing in $k$ for $k>3$. $\endgroup$ – Josiah Park Oct 14 '18 at 4:13
  • 2
    $\begingroup$ It seems that the sequence $Δ_k$ is an automatic sequence in base 3. $\endgroup$ – Bullet51 Oct 14 '18 at 6:01
  • 1
    $\begingroup$ Second differences might be simpler... $\endgroup$ – მამუკა ჯიბლაძე Oct 16 '18 at 5:40
28
$\begingroup$

It seems that the sequence $Δ_i$ can be computed by a finite state machine for $k = 3$: enter image description here

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$.

$\endgroup$
  • $\begingroup$ +1 for unmasking the pattern so neatly, if correct... but I have to be honest about not having checked the details. $\endgroup$ – Yaakov Baruch Oct 14 '18 at 12:14
  • 2
    $\begingroup$ Amazingly this method seems to work up to $\Delta_{10^8}$. Was your construction empirically based, or was there some mathematical insight involved? It is most interesting how one can justify this method, and whether it extends to larger values of $k$. $\endgroup$ – Mikhail Tikhomirov Oct 14 '18 at 14:57
  • $\begingroup$ @MikhailTikhomirov The construction was found by splitting the differences into groups of 3, 9, 27, etc. and attempting to characterize the non-periodic columns. There is only a little mathematical insight involved. $\endgroup$ – Bullet51 Oct 14 '18 at 15:47
  • $\begingroup$ It is interesting if one applies the process to odd integers instead of all integers. Here the behavior of the size of the difference set $\Delta^{(k)}=\{x_{i+1}-x_{i}\}$ alternates. The case for $k=2$ for odd integers resembles $k=3$ for the set of all integers. Five differences appear ($\{4,5,6,7,8\}$). The first few terms are $5, 7, 4, 8, 5, 6, 5, 8, 5, 7, 4, 8, 4, 7, 5, 8, 5,...$ $\endgroup$ – Josiah Park Oct 15 '18 at 1:07
6
+50
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Not an answer, but following the idea of Bullet and using the odd integers for $A$ instead gives the state diagram below for $k=2$ which (it seems) can be used to find $\Delta^{(k)}_{i}$.

enter image description here

As in Bullet's answer the directions at each level are given by $S_{n}$, the $n$-th digit from the right in the quaternary expansion of $i$, and when the digit $S_n$ does not appear in any of the outward pointing arrows from a vertex one terminates at the present node.

Edit: It has been pointed out by @მამუკაჯიბლაძე the earlier diagram had problems as early as $i=27$. After attempting to fix these problems, a new diagram was made which also had a minor problem (see comments). This is the latest diagram (but remains unchecked for large $i$). Here are the first 320 values in groups of $16$:

5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 6 5 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
5 7 4 8 5 6 5 8 5 7 4 8 4 7 5 8
5 7 4 8 4 7 5 8 5 6 5 8 4 7 5 8
$\endgroup$
  • 2
    $\begingroup$ But according to the OP for $k=2$ one gets $x_i=3i$, no? $\endgroup$ – მამუკა ჯიბლაძე Oct 15 '18 at 4:52
  • 2
    $\begingroup$ Also for $n=27$ (digits $123$) if I am not mistaken one must get $5$ while the machine gives $4$ $\endgroup$ – მამუკა ჯიბლაძე Oct 15 '18 at 8:51
  • 2
    $\begingroup$ @მამუკაჯიბლაძეThe diagram has now been updated to account for your observations. $\endgroup$ – Josiah Park Oct 15 '18 at 22:19
  • 2
    $\begingroup$ Seems to work up to 100000, i. e. up to about 8 quaternary digits. Since there are loops, does not mean much though... $\endgroup$ – მამუკა ჯიბლაძე Oct 15 '18 at 23:08
  • 3
    $\begingroup$ Verified to $10^8$. We still lack understanding why this sort of construction works at all... $\endgroup$ – Mikhail Tikhomirov Oct 16 '18 at 0:26
2
$\begingroup$

Here is another way of studying these processes. In the sequel $k=3$ but it is clear how to generalize.

The idea is to look at the matrices formed by three consecutive triples used in the insertion process. To this end we write the triples produced by the process into an infinite matrix $S$ with $3$ columns (indexed by 0,1,2), and rows indexed $1,2,,\ldots$. The $i$-th row of $S$ consists of the triple (in order) which sums to $x_i$.

So the top of $S$ is

\begin{align*} \begin{matrix} c0&c1&c2&\;\;x\\ 1&2&3&\;\;6\\ 4&5&6&\;\;15\\ 6&7&8&\;\;21\\ 9&10&11&\;\;30\\ 12&13&14&\;\;39\\ \ldots \end{matrix}\end{align*}

We let $M(n)$ be the $3\times 3$ submatrix of $S$ which consists of the rows $3n-1,3n,3n+1$ of $S$, and let $T_0(n),T_1(n),T_2(n)$ be the $3 \times 3$ matrices \begin{align*} T_0(n):=\begin{pmatrix} 8n-4 & 8n-3 & 8n-2\\ 8n-2 & 8n-1 & 8n\\ 8n+1 & 8n+2 & 8n+3\\ \end{pmatrix},\;\; T_2(n):=\begin{pmatrix} 8n-4 & 8n-3 & 8n-3\\ 8n-2 & 8n-1 & 8n\\ 8n+1 & 8n+2 & 8n+3\\ \end{pmatrix}\,\;\end{align*} \begin{align*} T_1(n):=\begin{pmatrix} 8n-4 & 8n-3 & 8n-2\\ 8n-1 & 8n-1 & 8n\\ 8n+1 & 8n+2 & 8n+3\\ \end{pmatrix}\;\;. \end{align*}

Our aim is to show:

Lemma: for all $n$ $$M(n)\in\{T_0(n),T_1(n),T_2(n)\}$$

Auxiliary considerations:

(1) Insertion of $x_n$. $x_n$ is inserted after the first appearance of its value. Since $n-1+x_n$ elements of $S$ are less or equal than $x_n$ $x_n$ will be inserted in row $\lceil{n+x_n \over 3}\rceil$ and in column $(n+x_n-1)\bmod 3$.

(2) Succession rules. Assume that $M(j)=T_i(n)$. Where will the produced $x$s be inserted? Application of the insertion rule gives:

for $i=0$ :

$x_{3j-1}$ goes to row $8n-3+j$ , colummn $1$. $x_{3j}$ goes to row $8n-1+j$ , colummn $2$.
$x_{3j+1}$ goes to row $8n+3+j$ , colummn $0$.

for $i=1$

$x_{3j-1}$ goes to row $8n-3+j$ , colummn $1$. $x_{3j}$ goes to row $8n-1+j$ , colummn $0$. $x_{3j+1}$ goes to row $8n+3+j$ , colummn $0$.

for $i=2$

$x_{3j-1}$ goes to row $8n-3+j$ , colummn $0$. $x_{3j}$ goes to row $8n-1+j$ , colummn $2$. $x_{3j+1}$ goes to row $8n+3+j$ , colummn $0$.

In other words: if $S(j)$ is of type $T_0$ it generates a type sequence $120$ later, type $T_1$ generates $100$, type $T_2$ generates $020$. .

Proof of the lemma:(sketch) comparison shows that $M(1)=T_0(1)$. Iterated use of the succession rules now shows that $(M(2),M(3),M(4))=(T_1(2),T_2(3),T_0(4))$, the next block of nine matrices has indices $100, 020, 120$, and in general the indices of a following $3^{k+1}$ block are generated by substituting $120$ for $0$, $100$ for $1$ and and $020$ for $2$ in the previous $3^k$ block. End of proof.

Some corollaries:

(1) for all n $$x_n\in \{8n-1,8n-2,8n-3\}$$ Thus $$1+\lfloor{n+x_n \over 3}\rfloor=3n\;\;.$$

(2) the row $3n+1$ is $8n+1,8n+2,8n+3$ and $x_{3n+1}=24n+6$

Open question: has the replicative sequence above a simple ternary description?


ADDED: the general case.

Slightly reformulating, we found above for $k=3$:

(1) the behaviour of $(x_n)$ is governed by the type sequence $(t_n)$, $x_n=8n-2$ if $t_n=0$, $x_n=8n-1$ if $t_n=1$, and $x_n=8n-3$ if $t_n=2$ (in the description above $t_n$ can be visualized as the column index of $x_n$)

(2) the sequence $(t_n)$ is the fixed point starting from $0$ of the $3$-uniform morphism $\phi$ of the free monoid $\{0,1,2\}^*$ given by $0\rightarrow 012,\;1\rightarrow 010,\;2\rightarrow 002$

The general case can be treated in the same way, giving:

(1) the behaviour of $(x_n)$ is governed by its type sequence $(t_n)$.

in case $k$ is odd:

$t_n\in\{-\tfrac{(k-1)}{2},\ldots,\tfrac{k-1}{2}\}$ (the representatives of the residues $\bmod \,k$ in $\{-\tfrac{(k-1)}{2},\ldots, \tfrac{k-1}{2}\}$) and for all $n$ $$x_n=(k^2-1)n-\tfrac{k(k-1)}{2} + 1 +t_n$$

(2a) let $b(0)=(0,1,2\ldots,k-1)$. For $p=1,..,\tfrac{k-1}{2}$ construct the word $b(p)$ from $b(0)$ by adding $p$ ($\bmod\,k$) to the value $\tfrac{k+1}{2}$ (leaving the rest unchanged). For $p=-\tfrac{(k-1)}{2},\ldots,-1$ construct the word $b(p)$ by adding $p$ ($\bmod k$) to the value ${k-1 \over 2}$ (leaving the rest unchanged).

Then the sequence $(t_n)$ (with representatives $0,1,\ldots,k-1$ $\bmod k$) is the fixed point starting from $0$ of the $k$-uniform morphism $\phi$ of the free monoid $\{0,1,\ldots,k-1\}^*$ given by $p\rightarrow b(p)$.

in case $k$ is even:

$t_n\in\{1,\ldots,k-1\}$ (i.e. $t_n=0$ does not happen), and for all $n$

$$x_n=(k^2-1)n-\tfrac{k^2}{2} + 1 +t_n$$

(2b) for $p\in \{0,\ldots k-1\}$ let $b(p)= (\tfrac{k}{2},\tfrac{k}{2}+1,\ldots k-1,p,1\ldots,\tfrac{k}{2}-1)$ (with $p$ at position $\tfrac{k}{2}+1$).

Then the sequence $(t_n)$ is the fixed point starting from $\tfrac{k}{2}$ of the $k$-uniform morphism $\phi$ of the free monoid $\{0,1,\ldots,k-1\}^*$ given by $p\rightarrow b(p)$.

By Cobham's theorem ("a sequence arising as (image under a coding of) a fixed point of a $k$-uniform morphism is $k$-automatic") the sequence $(t_n)$ is therefore $k$-automatic.
By the closure properties of the set of $k-$automatic sequences (under shifts, parallel generation and taking functions of output elements) then also the sequence $(\Delta_n)$ with $$\Delta_n=(k^2-1)+t_{n+1}-t_n=x_{n+1}-x_n$$ is $k$-automatic. (That is, $\Delta_n$ can be computed from the base-$k$ digits of $n$ with a finite state machine of the type desribed above.)

$\endgroup$
  • 4
    $\begingroup$ This is an interesting formulation! Just to note: this matrix representation is equivalent to the relation $x_{n′} \equiv y_n \pmod 3$ and the modular relation between $y_n$ and $\Delta_{n−1}$ given above. Similarly, the generalization of this should also come from the modular relations $\mod k$ $\endgroup$ – robinz16 Oct 27 '18 at 7:52
  • $\begingroup$ @robinz16: thanks, I wasn't aware of that (I was guided by the OP's remark that $x_{3n+1}=24n+6$). $\endgroup$ – esg Oct 28 '18 at 17:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.