2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "The number of longest suitable sequences appears to be k!×A002047[k]." Can you please explain this more or give an example. $\endgroup$ – Samdney Mar 28 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.