Is this contrived sequence eventually periodic?

Solution 1:

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.

Solution 2:

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?

Solution 3:

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.