13

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

ViHdzP
  • 4,582
  • 2
  • 18
  • 44
Nikita
  • 423
  • 1
    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. – ViHdzP Dec 05 '19 at 23:24
  • do you know this to be equivalent to the Collatz conjecture? – it's a hire car baby Dec 10 '19 at 10:17

3 Answers3

5

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.

ViHdzP
  • 4,582
  • 2
  • 18
  • 44
WhatsUp
  • 22,201
  • 19
  • 48
  • 1
    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. – ViHdzP Dec 07 '19 at 04:58
  • Something that I find very interesting is that many of the first rows for $n=27+360k$ coincide. For example, the first $183$ rows of $A(27)$ and of $A(3627)$ are identical. So, perhaps there's some sort of pattern to these entries, that only gets broken whenever the period isn't large enough? This behavior doesn't seem to occur with neither $87$ nor $147$, by the way. There's good reason to suspect these entries are for the most part uncontrollable. – ViHdzP Dec 07 '19 at 05:10
  • 2
    @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. – WhatsUp Dec 07 '19 at 13:16
  • 1
    @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 http://snippi.com/s/vcqbbj9 – Nikita Dec 07 '19 at 13:29
  • 1
    @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. – Nikita Dec 07 '19 at 13:32
  • 1
    @WhatsUp I edited your answer. If $A(27)$ really contains cycles of arbitrarily large lengths, we can use this to our advantage. – ViHdzP Dec 07 '19 at 16:07
  • 2
    @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. – WhatsUp Dec 07 '19 at 17:43
  • 1
    @URL $A(27)$ settles into simple pattern around row $729$ and from that point contains only cycles of length $4$ and $5$. The longest cycle in $A(27)$ is on row 420 of length 14. – Nikita Dec 07 '19 at 18:50
  • 1
    @URL You see, I guessed correctly that I shouldn't guess anymore! – WhatsUp Dec 07 '19 at 18:59
  • @WhatsUp Maybe my idea isn’t dead yet. If we could find an “ideal table” that does have arbitrarily large cycles, when a list of congruences, possible or impossible, holds, by my argument, we could find tables that coincide in an arbitrarily large amount of the first rows with the “ideal table”, whilst not being identical. This would then imply the existence of infinitely many possible tables, contradicting eventual periodicity. – ViHdzP Dec 07 '19 at 19:13
  • 1
    Another observation: If $A(n)$ has $m$-cycles of lengths $\ell_1,\ell_2,\ldots,\ell_k$, then $A$'s period must be at least $\text{lcm}\left(\ell_1,\ell_2,\ldots,\ell_k\right)$. This is because any other table $A(n+N)$ that is the same as this one must be so that $n+N$ gives the same residues mod these cycle lengths. By using this with $n=27$, which has cycles of all lengths up to $11$, and of length $13$ (at least according to my own code), if $A(n)$ is periodic, its period is at least $360360$. – ViHdzP Dec 09 '19 at 07:33
  • 1
    @URL according to WhatsUp's code and also my observations $A(27)$ has a cycle of length 14, but it doesn't contribute to $\text{lcm}\left(\ell_1,\ell_2,\ldots,\ell_k\right)$ since there are earlier cycles of lengths 7 and 2. The tree i posted earlier ((snippi.com/raw/vcqbbj9), unfortunately it got cropped at the end) shows that the period must be at least 5354228880, because $A(116446707)$ contains cycles of lengths $1, 2, 3, 5, 4, 9, 8, 7, 13, 11, 19, 17, 16, 23$. I think WhatsUp's observation that there's never a zero to the left of a non-zero is worth looking into. – Nikita Dec 09 '19 at 20:51
  • 1
    @Nikita This is actually a simple assertion to prove. Suppose that the first $n$ entries are non-zero. Then, if any entry exceeds $n+2$, it will just keep increasing every next step, indefinitely (as any number greater than $n$ behaves essentially the same in the $m$-cycle). This means that, if we’re ever to create more non-zero entries, our maximum entry must be $n+1$ when we do so, i.e. we must write to the $n+1$-th entry. – ViHdzP Dec 09 '19 at 21:12
  • 1
    @URL This gives me hope - if we can come up with a bunch of similar computer-checkable criteria for the end of complex evolution of the tape, and start of a simple pattern, the problem becomes easier to tackle computaionally. I can already close many branches of the aforementioned possibility tree with this "any entry exceeds $n+2$" criterion. – Nikita Dec 10 '19 at 11:24
3

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?

ViHdzP
  • 4,582
  • 2
  • 18
  • 44
2

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.

Nikita
  • 423