12
$\begingroup$

For a number $n$ we build an infinite table $A(n)_{ij}\;(i,j\ge0)$ such that: $$A(n)_{ij} = 0, \text{if } i = 0$$ and for each $i\ne0$ we build a sequence $m_{i0}..m_{i(n-1)}$ such that $m_{i0} = 0$ and $m_{i(a+1)} = A(n)_{(i-1)(m_{ia})}$ and set $$A(n)_{ij} = \begin{cases}A(n)_{(i-1)j}, & \text{for $j\ne m_{i(n-1)}$ } \\ A(n)_{(i-1)j}+1, & \text{for $j=m_{i(n-1)}$ } \end{cases}$$

Understanding the risk of making everything even less comprehensible, i'll try to describe the process differently: we have an infinite tape with zeroes on each cell. Then on every step we take 0th cell, look at the number on it, take cell with that index, repeat this n times, and then increment the number on the final cell.

Here's what i know about resulting tables: for all even $n$ the table is the same, for all $n\equiv5\pmod 6$ the table is the same and also for all $n\equiv1\pmod 6$ the table is the same.

The case when $n\equiv3\pmod 6$ is the odd one because the numbers $m_{10j}$ contain a cycle of length $5$, and it becomes too hard to check every case by hand.

My question is whether there is finite number of distinct tables for different $n$, and if they are eventually periodic, i. e. if there are numbers $N$ and $t$ such that for all $n > N$ $\forall ij. A(n)_{ij} = A(n+t)_{ij}$.

Edit: as per URL's advice, here's some examples.

For even $n$: $$ \begin{matrix} 0 & 0 & 0 & \ldots \\ 1 & 0 & 0 & \ldots \\ 2 & 0 & 0 & \ldots \\ 3 & 0 & 0 & \ldots \\ 4 & 0 & 0 & \ldots \\ \vdots & \vdots & \vdots & \end{matrix} $$

For $n\equiv1\pmod 6$: $$ \begin{matrix} 0 & 0 & 0 & \ldots \\ 1 & 0 & 0 & \ldots \\ 1 & 1 & 0 & \ldots \\ 1 & 2 & 0 & \ldots \\ 1 & 3 & 0 & \ldots \\ 1 & 4 & 0 & \ldots \\ \vdots & \vdots & \vdots & \end{matrix} $$

For $n = 3$:

$$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 2 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 2 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 2 & 1 & 0 & 0 & 0 & \ldots \\ 2 & 2 & 2 & 0 & 0 & 0 & \ldots \\ 2 & 2 & 3 & 0 & 0 & 0 & \ldots \\ 3 & 2 & 3 & 0 & 0 & 0 & \ldots \\ 3 & 2 & 3 & 1 & 0 & 0 & \ldots \\ 3 & 2 & 4 & 1 & 0 & 0 & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\ 3 & 2 & i-3 & 1 & 0 & 0 & \ldots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\ \end{matrix} $$

For $n\equiv5\pmod 6$: $$ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & \ldots\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & \ldots\\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & \ldots\\ 1 & 2 & 0 & 0 & 0 & 0 & 0 & \ldots\\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & \ldots\\ 1 & 3 & 1 & 0 & 0 & 0 & 0 & \ldots\\ 1 & 3 & 1 & 1 & 0 & 0 & 0 & \ldots\\ 1 & 4 & 1 & 1 & 0 & 0 & 0 & \ldots\\ 1 & 4 & 1 & 1 & 1 & 0 & 0 & \ldots\\ 1 & 5 & 1 & 1 & 1 & 0 & 0 & \ldots\\ 1 & 5 & 1 & 1 & 1 & 1 & 0 & \ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\ \end{matrix}$$

$\endgroup$
  • 1
    $\begingroup$ I think the tape explanation makes much more sense. By the way, it might be useful to add some tables for small $n$. It might give some useful insight for those who want to try this problem out. $\endgroup$ – URL Dec 5 '19 at 23:24
  • $\begingroup$ do you know this to be equivalent to the Collatz conjecture? $\endgroup$ – samerivertwice Dec 10 '19 at 10:17
5
$\begingroup$

I have written a small piece of code to calculate these tables.

At first I thought I found that $A(n) = A(n + 30)$, but that seems to be wrong for $n \equiv 21, 27\pmod {30}$.

Increasing the period to $60$, it's still wrong for $n \equiv 27 \pmod{60}$, but correct for all other values.

Therefore, if a period exists, it must be multiple of $60$. So I guessed that if I increase the period further, I would find an even larger period for $n \equiv 27 \pmod{60}$.


Wrong! It seems that, $A(27)$ is unique, at least among $A(1)$ to $A(1000)$. This means that there is no other $n$ in the range $[1, 1000]$ such that $A(27) = A(n)$.

And the same for $A(87)$: it's again unique among $A(1)$ to $A(1000)$. And the same for $A(147)$.

Of course, at this point I guessed that every $A(n)$ for $n \equiv 27\pmod{60}$ is unique.


Wrong again! For $n \equiv 207, 327 \pmod{360}$, we have $A(n) = A(n + 360)$. Except these two cases, the $A(n)$'s for $n\equiv 27\pmod{60}$ do seem to be unique.

The conclusion is that it is perhaps not eventually periodic, or it could be periodic with a very large period, or some other kind of "periodic rule". In short, there is no conclusion.

And my final guess is that I shouldn't guess anymore.


Since I don't have any cross-checks, it could also be that there are bugs in my codes. Interested people may implement their own versions to check my claims here.

The code I used, written in python for no reason:

for calculating a particular $A(n)$:

def U(n):
    u = []
    a = []
    for i in range(BD):
        u.append(list(a))
        #print(a)
        k = 0
        for i in range(n):
            kk = 0
            if k < len(a): kk = a[k]
            k = kk
        if k >= len(a):
            a += [0] * (k - len(a) + 1)
        a[k] += 1
    return u

for comparing two $A(n)$'s:

def Comp(u, v):
    for i in range(BD):
        ui = u[i]
        vi = v[i]
        if len(ui) > len(vi):
            ui, vi = vi, ui
        for j in range(len(ui), len(vi)):
            if vi[j] != 0: return False
        for j in range(len(ui)):
            if ui[j] != vi[j]:
                return False
    return True

Here BD is the number of rows to compute. I use BD = 400 for most of the experiments.

Edit: It seems like the $m$ cycles of $A(27)$ grow arbitrarily large in period. (Edit #2: they actually don’t, since as @Nikita points out, they enter a regular pattern after row $729$. But maybe, the general idea is still useful.) If this was true (for $27$ or some other number), we could order their periods in order of appearance as $k_1,k_2,\ldots$ – this sequence would have arbitrarily large entries. Now, if for an integer $n$, we built $N=27+\text{lcm}\left(k_1,k_2,\ldots,k_n\right)$, $A(N)$ would have the same first cycle lengths as $A(27)$, but it wouldn’t be able to equal any previous table. This would immediately contradict eventual periodicity.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I have my own code, and I can confirm your observations. That's quite a bummer, since there are a lot of very neat patterns that can be created by using the other congruences. $\endgroup$ – URL Dec 7 '19 at 4:58
  • 2
    $\begingroup$ @URL To be honest, I didn't put too much mathematical thought into this, just played with the experiments. There are some phenomena to prove, e.g. there's never a zero to the left of a non-zero. $\endgroup$ – WhatsUp Dec 7 '19 at 13:16
  • 1
    $\begingroup$ @URL I also ran some code and it seems for example that when $n=116446707 + 232792560k$, there is a cycle of m's of length $23$ on row $1806$ so everything branches out even further. It's just so weird that everything is tame and predictable unless $n = 27 + 30k$ and then it's just wild. I left a tree of choices for large n at snippi.com/s/vcqbbj9 $\endgroup$ – Nikita Dec 7 '19 at 13:29
  • 1
    $\begingroup$ @URL the row 183 is the first row where m's make a cycle of length 7. 27 and 3627 have different remainders when divided by 7, but all the same remainders when divided by lengths of earlier cycles (namely 2, 3, 4, 9 and 8), so their tables coincide until then. $\endgroup$ – Nikita Dec 7 '19 at 13:32
  • 2
    $\begingroup$ @URL From a more systematic point of view, the issue I see is that there is not much mathematical theory applicable here. My feeling is that, by allowing different initial status, this problem is comparable to some cellular automata, such as the game of life, or Lanton's ant. There are often unexpected complexity in these problems, which we unfortunately don't have enough tool to analyze, except for some computational trick to efficiently simulate them. But this is definitely an interesting problem to study, and I suggest a cross-post to MathOverFlow for attracting more attentions. $\endgroup$ – WhatsUp Dec 7 '19 at 17:43
3
$\begingroup$

Probably not. As @WhatsUp explains, certain specific congruences seem to cause lots of trouble. However, most of them seem to have a very regular structure. Here's all of the tables for congruences mod $60$, excluding the problematic $60k+27$, and $60k+51$ (since for the love of me, I can't figure out the pattern).

(Trailing zeros removed for clarity).

$n=2k$: $$ \begin{array} \\ 1 \\ 2 \\ 3 \\ \vdots \\ i \\ \vdots \end{array} $$

$n=6k+1$: $$ \begin{array} \\ 1 \\ 1 & 1 \\ 1 & 2 \\ \vdots & \vdots \\ 1 & i \\ \vdots & \vdots \end{array} $$

$n=6k+5$: $$ \begin{array} \\ 1 \\ 1 & 1 \\ 1 & 2 \\ 1 & 2 & 1 \\ 1 & 3 & 1 \\ 1 & 3 & 1 & 1 \\ 1 & 4 & 1 & 1 \\ 1 & 4 & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & i & 1 & 1 & 1 & \ldots & (i-1\ 1\text{'s}) \\ 1 & i+1 & 1 & 1 & 1 & \ldots & (i-1\ 1\text{'s}) \\ \vdots & \vdots & \vdots & \vdots & \vdots \end{array} $$

$n=30k+3$: $$ \begin{array} \\ 1 \\ 1 & 1 \\ 1 & 2 \\ 2 & 2 \\ 2 & 2 & 1 \\ 2 & 2 & 2 \\ 2 & 2 & 3 \\ 3 & 2 & 3 \\ 3 & 2 & 3 & 1 \\ 3 & 2 & 4 & 1 \\ 3 & 2 & 5 & 1 \\ \vdots & \vdots & \vdots & \vdots \\ 3 & 2 & i & 1 \\ \vdots & \vdots & \vdots & \vdots \end{array} $$

$n=30k+9$: $$ \begin{array} \\ 1 \\ 1 & 1 \\ 1 & 2 \\ 2 & 2 \\ 2 & 2 & 1 \\ 2 & 2 & 2 \\ 2 & 2 & 3 \\ 3 & 2 & 3 \\ 3 & 2 & 3 & 1 \\ 3 & 2 & 4 & 1 \\ 3 & 2 & 4 & 1 & 1 \\ 3 & 2 & 5 & 1 & 1 \\ 3 & 2 & 5 & 1 & 1 & 1 \\ 3 & 2 & 6 & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 3 & 2 & i & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ 3 & 2 & i+1 & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array} $$

$n=30k+15$: $$ \begin{array} \\ 1 \\ 1 & 1 \\ 1 & 2 \\ 2 & 2 \\ 2 & 2 & 1 \\ 2 & 2 & 2 \\ 2 & 2 & 3 \\ 3 & 2 & 3 \\ 3 & 2 & 3 & 1 \\ 3 & 2 & 4 & 1 \\ 4 & 2 & 4 & 1 \\ 4 & 2 & 4 & 1 & 1 \\ 4 & 2 & 5 & 1 & 1 \\ 5 & 2 & 5 & 1 & 1 \\ 5 & 2 & 5 & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ i & 2 & i & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ i & 2 & i+1 & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ i+1 & 2 & i+1 & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array} $$

$n=60k+21$: $$ \begin{array} \\ 1 & \\ 1 & 1 \\ 1 & 2 \\ 2 & 2 \\ 2 & 2 & 1 \\ 2 & 2 & 2 \\ 2 & 2 & 3 \\ 3 & 2 & 3 \\ 3 & 2 & 3 & 1 \\ 3 & 2 & 4 & 1 \\ 3 & 2 & 4 & 2 \\ 3 & 2 & 4 & 3 \\ 3 & 2 & 4 & 4 \\ 4 & 2 & 4 & 4 \\ 4 & 2 & 4 & 4 & 1 \\ 4 & 2 & 5 & 4 & 1 \\ 4 & 2 & 5 & 4 & 2 \\ 4 & 2 & 5 & 4 & 3 \\ 4 & 2 & 5 & 4 & 4 \\ 4 & 2 & 5 & 4 & 5 \\ 5 & 2 & 5 & 4 & 5 \\ 5 & 2 & 5 & 4 & 5 & 1 \\ 5 & 2 & 6 & 4 & 5 & 1 \\ 5 & 2 & 6 & 4 & 5 & 2 \\ 5 & 2 & 6 & 4 & 5 & 3 \\ 5 & 2 & 6 & 4 & 6 & 3 \\ 5 & 2 & 6 & 4 & 6 & 4 \\ 5 & 2 & 6 & 4 & 6 & 5 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 2i & 2 & 2i & 4 & 2i & 6 & \ldots & 2i & 2i \\ 2i & 2 & 2i & 4 & 2i & 6 & \ldots & 2i & 2i & 1 \\ 2i & 2 & 2i+1 & 4 & 2i & 6 & \ldots & 2i & 2i & 1\\ 2i & 2 & 2i+1 & 4 & 2i & 6 & \ldots & 2i & 2i & 2\\ 2i & 2 & 2i+1 & 4 & 2i & 6 & \ldots & 2i & 2i & 3\\ 2i & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i & 2i & 3\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots \\ 2i & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1\\ 2i+1 & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 \\ 2i+1 & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 1\\ 2i+1 & 2 & 2i+2 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 1\\ 2i+1 & 2 & 2i+2 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 2\\ 2i+1 & 2 & 2i+2 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 3\\ 2i+1 & 2 & 2i+2 & 4 & 2i+2 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 3\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots \\ 2i+1 & 2 & 2i+2 & 4 & 2i+2 & 6 & \ldots & 2i+1 & 2i & 2i+2 & 2i+1\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots \\ \end{array} $$

$n=60k+57$: $$ \begin{array} \\ 1 & \\ 1 & 1 \\ 1 & 2 \\ 2 & 2 \\ 2 & 2 & 1 \\ 2 & 2 & 2 \\ 2 & 2 & 3 \\ 3 & 2 & 3 \\ 3 & 2 & 3 & 1 \\ 3 & 2 & 4 & 1 \\ 3 & 3 & 4 & 1 \\ 3 & 3 & 4 & 2 \\ 3 & 3 & 4 & 3 \\ 3 & 3 & 4 & 4 \\ 4 & 3 & 4 & 4 \\ 4 & 3 & 4 & 4 & 1 \\ 4 & 3 & 4 & 5 & 1 \\ 4 & 4 & 4 & 5 & 1 \\ 4 & 4 & 4 & 5 & 2 \\ 4 & 4 & 4 & 5 & 3 \\ 4 & 4 & 4 & 5 & 4 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ i & i & i & i & i & \ldots & (i-1\ i\text{'s}) & \ldots & i+1 & i+1 \\ i+1 & i & i & i & i & \ldots & (i-2\ i\text{'s}) & \ldots & i+1 & i+1 \\ i+1 & i & i & i & i & \ldots & (i-2\ i\text{'s}) & \ldots & i+1 & i+1 & 1\\ i+1 & i & i & i & i & \ldots & (i-2\ i\text{'s}) & \ldots & i+1 & i+2 & 1\\ i+1 & i+1 & i & i & i & \ldots & (i-3\ i\text{'s}) & \ldots & i+1 & i+2 & 1\\ i+1 & i+1 & i & i & i & \ldots & (i-3\ i\text{'s}) & \ldots & i+1 & i+2 & 2\\ i+1 & i+1 & i+1 & i & i & \ldots & (i-4\ i\text{'s}) & \ldots & i+1 & i+2 & 2\\ \vdots & \vdots & \vdots & \vdots & \vdots & & & & \vdots & \vdots \\ i+1 & i+1 & i+1 & i+1 & i+1 & \ldots & (i\ (i+1)\text{'s}) & \ldots & i+2 & i-2\\ i+1 & i+1 & i+1 & i+1 & i+1 & \ldots & (i\ (i+1)\text{'s}) & \ldots & i+2 & i-1\\ i+1 & i+1 & i+1 & i+1 & i+1 & \ldots & (i\ (i+1)\text{'s}) & \ldots & i+2 & i\\ i+1 & i+1 & i+1 & i+1 & i+1 & \ldots & (i\ (i+1)\text{'s}) & \ldots & i+2 & i+1\\ \vdots & \vdots & \vdots & \vdots & \vdots & & & & \vdots & \vdots \\ \end{array} $$

Proving that these tables match their descriptions is an incredibly tedious induction exercise. Not so much as it might initially seem, though, since the $m$ sequences you defined turn out to always have relatively small periods in these cases. Perhaps we should be hopeful for the remaining ones?

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Definition. Support of the tape is the number of nonzero cells on the tape.

So far every checked (by hand) table falls into one of three patterns (Edit: $n=10887$ doesn't seem to fall into any of these cases):

  1. One cell (or column) just increasing indefinitely. Example for $n = 7$: $$\begin{array} \\ 1 \\ 1 & 1 \\ 1 & 2 \\ 2 & 2 \\ 2 & 2 & 1 \\ 2 & 2 & 2 \\ 2 & 2 & 3 \\ 3 & 2 & 3 \\ 3 & 2 & 3 & 1 \\ 3 & 2 & 4 & 1 \\ 3 & 2 & 5 & 1 \\ \vdots & \vdots & \vdots & \vdots \\ 3 & 2 & i & 1 \\ \vdots & \vdots & \vdots & \vdots \end{array}$$
  2. There is some amount of cells with values equal to the support of the tape among some random constant cells, and a growing number of cells equal to some small number $w$ to the right. Example for $n=15$: $$\begin{array} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ i & 2 & i & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ i & 2 & i+1 & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ i+1 & 2 & i+1 & 1 & 1 & 1 & \ldots & (i-2\ 1\text{'s}) \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array}$$ In this example $w=1$.
  3. (Edit: this case was generalized after I found $n$ that didn't conform to previous version) Some random cells in the beginning, then cells with number $s$ spaced by regular intervals $j$ filled so that value of cell $a+j$ is larger than value of cell $a$ by $j$, where $s$ is the support. This is a tricky one, here is an example for $n = 21$: $$\begin{array} \\ \vdots \\ 2i & 2 & 2i & 4 & 2i & 6 & \ldots & 2i & 2i \\ 2i & 2 & 2i & 4 & 2i & 6 & \ldots & 2i & 2i & 1 \\ 2i & 2 & 2i+1 & 4 & 2i & 6 & \ldots & 2i & 2i & 1\\ 2i & 2 & 2i+1 & 4 & 2i & 6 & \ldots & 2i & 2i & 2\\ 2i & 2 & 2i+1 & 4 & 2i & 6 & \ldots & 2i & 2i & 3\\ 2i & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i & 2i & 3\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots \\ 2i & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1\\ 2i+1 & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 \\ 2i+1 & 2 & 2i+1 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 1\\ 2i+1 & 2 & 2i+2 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 1\\ 2i+1 & 2 & 2i+2 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 2\\ 2i+1 & 2 & 2i+2 & 4 & 2i+1 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 3\\ 2i+1 & 2 & 2i+2 & 4 & 2i+2 & 6 & \ldots & 2i+1 & 2i & 2i+1 & 3\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots \\ 2i+1 & 2 & 2i+2 & 4 & 2i+2 & 6 & \ldots & 2i+1 & 2i & 2i+2 & 2i+1\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots \\ \end{array}$$ In this example $i = 2$.

With the help from URL, I have taught my computer to recognize cases 1 and 2 when $w=1$ (Edit: for all $w$). If we find criteria for the remaining cases, checkable by a computer, we can cross off many many cases. It might not give us the final answer about periodicity, but it will probably be a big step in the direction of the answer.

All the MathJax is copied from URL's answer but cropped for reader's convenience.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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