Distinct distances between adjacent equal elements

Question

Let's call a sequence $a_1, \ldots, a_n$ suitable if for any positive integer $d$ there is at most one index $i$ such that $a_i = a_{i + d}$ and all elements $a_{i + 1}, \ldots, a_{i + d - 1}$ are not equal to $a_i$.

For each $k$, I'm interested in longest suitable sequences with all elements in $\{0, \ldots, k - 1\}$. There is a suitable sequence of length $3k - 1$: start with numbers $0, \ldots, k - 1$ in order, followed by first $2k - 1$ elements of A025480. E.g., for $k = 3$ this sequence would look as follows: $0, 1, 2, 0, 0, 1, 0, 2$. It isn't difficult to prove that this pattern works for any $k$.

With brute-force I've discovered a few curious observations:

• $3k - 1$ appears to be the maximum length of a suitable sequence with elements in $\{0, \ldots, k - 1\}$;
• The number of longest suitable sequences appears to be $k! \times $A002047$[k]$.

How can this be explained?

Answer 1

This can be explained as follows.

Assume that $(a_1,\ldots,a_{n})$ is a suitable sequence. For every $j\in \{0,\ldots,k-1\}$ denote $A(j)=\{i:a(i)=j\}$ and denote by $m(i)$ and $M(i)$ the minimal and maximal, respectively, elements of $A(j)$. Then $$\sum_{j=0}^{k-1} \left(M(i)-m(i)\right)\geqslant 1+2+\ldots+(n-k),$$ since LHS equals to the sum of distances between adjacent equal elements, and there are at least $n-k$ such distances (exactly $n-k$ if $A(j)\ne \emptyset$ for all $j$). Since all guys $m(j)$ are distinct, their sum is at least $1+2+\ldots+k$, analogously the sum of $M(j)$ is at most $(n-k+1)+\ldots+n$, thus $$ \sum_{j=0}^{k-1} M(i)-m(i)\leqslant (n-k+1)+\ldots+n-(1+\ldots+k)=k(n-k),$$ and we get $k(n-k)\geqslant 1+\ldots+n-k=(n-k)(n-k+1)/2$, or $n\leqslant 3k-1$.

Also we get that if $n=3k-1$ is the length of a suitable sequence $(a_1,\ldots,a_{3k-1})$, then this may be only possible if $a_1,\ldots,a_k$ are all distinct, and so are $a_{2k-1},\ldots,a_{3k-1}$. For $s=1,2,\ldots,2k-1$ denote by $f(i)$ the minimal positive number such that $a_i=a_{i+f(i)}$. Then $f(1),\ldots,f(2k-1)$ are well-defined and form a permutation of $1,\ldots,2k-1$. Also the numbers $i+f(i)$ must form a permutation of $k+1,\ldots,3k-1$. And if this all happens, we get $k!$ corresponding suitable sequences. It remains to note that then $(i-k,f(i)-k,2k-i-f(i))$ for $i=1,2,\ldots,2k-1$ are the columns of a $3\times (2k-1)$ zero-sum array (see definition atA002074), and viceversa.

Answer 2

You can do the following considerations, at first for the Grundy values (A025480) which are given by

$a\left(2n\right) = n \quad \mathrm{and} \quad a\left(2n+1\right) = a\left(n\right)$

At first, we will define $m^{e} := 2n$ (m is even) respectively $m^{o} := 2n + 1$ (m is odd) and hence, we can rewrite this to

$a\left(m^{e}\right) = \frac{m^{e}}{2} \quad \mathrm{and} \quad a\left(m^{o}\right) = a\left(\frac{m^{o}-1}{2}\right)$

If we look at our examples and the definition of Grundy values, we see that starting by any $m^{o}$ the calculation of the final element stops if we reach a $m^{e}$ after an certain number of odd $m^{o}$'s. So, the $m^{e}$ are our termination cases of element computation.

We will determine an equation which connects the starting element $m_{1}^{o}$ with the final termination element $m_{i+1}^{e}$.

For this we get in general for only odd steps: $m_{i}^{o} = \frac{m_{1}^{o} - \sum_{k=0}^{i-2}2^{k}}{2^{i-1}}\\ = \frac{m_{1}^{o} - 2^{0} - \sum_{k=1}^{i-2}2^{k}}{2^{i-1}}\\ = \frac{m_{1}^{o} - 1 - 2\frac{2^{i-2} - 1}{2 - 1}}{2^{i-1}}\\ = \frac{m_{1}^{o} - 2^{i-1} + 1}{2^{i-1}}$

for all $i \geq 2$, $n \in \mathbb{N}$. To determine the final sequence element, we have to do one even step: $n_{i+1}^{e} = \frac{m_{1}^{o} - 2^{i-1} + 1}{2^{i-1}} \cdot \frac{1}{2}\\ = \frac{\left(2n_{1}^{o} + 1\right) - 2^{i-1} + 1}{2^{i}}\\ = \frac{2n_{1}^{o} - 2^{i-1} + 2}{2^{i}}\\ = \frac{n_{1}^{o} - 2^{i-2} + 1}{2^{i-1}}$

with $m_{1}^{o} = 2n_{1}^{o} + 1$ and $m_{i}^{e} = 2n_{i+1}^{e}$. We will solve the equation for $n_{1}^{o}$:

$2^{i-1}n_{i+1}^{e} = n_{1}^{o} - 2^{i-2} + 1$

$n_{1}^{o} = 2^{i-1}n_{i+1}^{e} + 2^{i-2} - 1$

Now, we want to use the result from above for some distance examinations.

We want to determine the first appearances of a particular number within the Grundy sequence.

At first at all, we have the first appearance of a number simple given by an even step. So, $n_{i+1}^{e}$ appears for $m_{i+1}^{e} = 2n_{i+1}^{e}$, because of $a\left(m_{i+1}^{e}\right) = a\left(2n_{i+1}^{e}\right) = n_{i+1}^{e}$.

So, to determine when this number $n_{i+1}^{e}$ appears the next, second time, within the Grundy sequence, we simple have take the equation for $i=2$:

$n_{1,1}^{o} = 2^{2-1}n_{i+1}^{e} + 2^{2-2} - 1\\ = 2n_{i+1}^{e}$

Next, we are interested in the positions of sequence elements.

The position $pos$ of a number $n_{i+1}^{e}$ within a simple integer sequence $0,1, \dots, k-2, k-1$ is given by

$n_{i+1,pos}^{e} = n_{i+1}^{e}$

and the position $pos$ of numbers $n_{i}^{u}$ respectively $n_{i}^{e}$ are given by

$n_{i,pos}^{o} = 2n_{i}^{o} + 2 \quad \mathrm{and} \quad n_{i,pos}^{e} = 2n_{i}^{e} + 1$

Now, we want to calculate the position distance for our given problem statement sequence.

$|n_{1,1,pos}^{o} - n_{i+1,pos}^{e}| = 2n_{1}^{o} + 2 - n_{i+1}^{e}\\ = 2\left(2n_{i+1}^{e}\right) + 2 - n_{i+1}^{e}\\ = 4n_{i+1}^{e} + 2 - n_{i+1}^{e}\\ = 3n_{i+1}^{e} + 2$

We start counting the sequence by $1$. Since we want to have a look at the original problem statement with a given pre-sequence $\{0,1,\dots, k-2,k-1\}$, we have to resubstitute the solution by $n_{i+1}^{e} - 1$ to

$|n_{1,1,pos}^{o} - n_{i+1,pos}^{e}| = 3\left(n_{i+1}^{e} - 1\right) + 2\\ = 3n_{i+1}^{e} - 3 + 2\\ = 3n_{i+1}^{e} - 1$

I also wrote it all together in a pdf version with some additional calculations. You can find it here: more detailed pdf Version