# Distinct distances between adjacent equal elements

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?

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