A year or two ago I was fiddling around with sequences and I stumbled upon a family of sequences that seem to have some interesting properties. The family, $\mathcal{S}$, is defined as follows:
$$ f\in\mathcal{S} \iff f : \mathbb{Z}\rightarrow\mathbb{N} \land \forall n\in\mathbb{Z}. f(n+1) = f(n-f(n)) $$
That is to say if we wish to find the result of the sequence at $n$ we look at the number before it and take that many steps back, whatever is there is the value at $n$.
Here are a couple of examples of such sequences to help you get the idea:
$\dots 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 \dots$
$\dots 2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1 \dots$
$\dots 4,2,2,4,2,2,4,2,2,4,2,2,4,2,2,4,2,2 \dots$
Now there are a couple of simple things we can quickly prove about these sequences.
If there are $n+1$ instances of $n$ in a row the whole sequence must only be $n$.
If $m\leq n$ and there is an $m$ followed by $n$ $n$s in a row then the sequence must be that and only that repeated.
Theses are all easy enough to show, but the thing I've wanted to know for about a year is how periodic are these sequences? There are two conjectures I have about these sequences, a weak one I believe is true and strong one I believe is false.
Weak conjecture
If a sequence in family $\mathcal{S}$ is bounded then it must be periodic.
Strong conjecture
All sequences in family $\mathcal{S}$ are periodic.
I have so far been unable to show either. I started to construct a sequence to disprove the second theorem but it was very tricky. I started with a seed filled with gaps. I kept adding numbers to the gaps to try to make sure there was always space for more gaps. It seemed to work but every so often I would run into an issue and have to go back and change a choice I made. I was never able to find a method that was guaranteed to generate a sequence that obeyed the rule.
So now that I've had my fun I wanted to see if anyone else had some thoughts. Can anyone prove or disprove either of the conjectures?
Here is a proof of the weak conjecture:
Suppose the terms of $f$ are all strictly less than $M$. Then each term of $f$ depends only on the previous $M$ terms. There are only $M^2$ possibilities for the last $M$ terms, so if we write out any $M^2 + M - 1$ consecutive terms of $f$, we must observe two indices $n < n'$ such that the subsequences $f(n), \dotsc, f(n+M-1)$ and $f(n'), \dotsc, f(n'+M-1)$ are identical. This implies that beyond index $n$, $f$ is periodic with period dividing $n'-n$. Since we can start our $M^2 + M - 1$ consecutive terms arbitrarily far to the left, $f$ must be periodic everywhere.