Show this function on sequences is cyclical.
Given a sequence $f$ define a new sequence $\phi f$ as follows:
$$ \phi f(n):=\text{card }\{k\in\mathbb{N}_{\leq{n}}\mid f(k)=f(n)\}$$
where $\text{card}$ is the set cardinality function. In other words $\phi f(n)$ counts up how often $f(n)=f(k)$ for $k\leq n$. Also, we can iteratively apply $\phi$ to $f$. Here is an example:
$$\begin{array} \\ f & = & (a,&b,&a,&c,&b,&d,&a,&c,&a,&b,&...) \\ \phi f & = & (1,&1,&2,&1,&2,&1,&3,&2,&4,&3,&...) \\ \phi^2 f & = & (1,&2,&1,&3,&2,&4,&1,&3,&1,&2,&...) \\ \phi^3 f & = & (1,&1,&2,&1,&2,&1,&3,&2,&4,&3,&...) \\ \end{array}$$
Notice that $\phi f=\phi^3 f$, which via induction implies $\phi^nf=\phi^{n+2}f$ for all $n\in\mathbb{N}$
Conjecture : If $f$ is any sequence then $\phi^n f = \phi^{n+2} f$ for all $n\in\mathbb{N}$.
Very nice observation.
As you note, for the conjecture it suffices to prove $\phi^3=\phi$.
Call sequences $a=(a_1,a_2,\dots)$ and $b=(b_1,b_2,\dots)$ similar, if $\phi a=\phi b$, i.e. for each index $n$, $\ a_n$ occurs the same times among $a_1,\dots,a_n\ $ as $\ b_n$ among $b_1,\dots,b_n$.
For example, the sequences $(1,1,2,2,3,3,1),\ (1,1,2,2,3,3,2),\ (1,1,2,2,3,3,3)$ are similar.
We have to show that $\phi^2 a$ is similar to $a$ for an arbitrary sequence $a$.
Assume it holds for $n$ long sequences, and take $a_{n+1}$ in $a=(a_1,\dots,a_{n+1})$.
- It is either a 'new element' ($\phi a(n+1)=1$), in which case the number of $1$'s that denotes the new elements, is increased by one in $\phi a$, implying $\phi^2 a(n+1)=|\{a_1,\dots,a_{n+1}\}|$ which is a new element in the sequence $\phi^2a$.
- Or, it is a repeating element, and $s:=\phi a(n+1)=|\{i\le n+1:a_i=a_{n+1}\}|$.
This $s$ occurs in $\phi a$ for exactly $q$ times, where $q$ is the number of $a_i$'s occuring exactly $s$ times in $a$. (If $s$ is new, then $q=1$, and $a_{n+1}$ can be replaced by any of these $a_i$'s to get a similar sequence.)
On one hand, it means $\phi^2 a(n+1)=q$.
On the other hand, $q$ already occured in $\phi^2 a(1,\dots,n)$ exactly $s-1=|\{i\le n:a_i=a_{n+1}\}|$ times.
Another approach
Call a sequence $a$ of positive integers a regular sequence, if for all $n$,
- $\ 1\le a_n\le\max_{i<n}a_i+1$
- In every initial segment of $a$, the number of $x$'s is at least the number of $y$'s whenever $x\le y$.
Note that 2. can be rephrased as: if $a_n=a_i$ for some $i<n$, then $a_n$ is minimal among those sequence elements which occur exactly $(\phi a)_n-1$ times in $(a_1,\dots,a_{n-1})$
[because $a_n$ in $(a_1,\dots,a_n)$
has one more occurances than any of them].
For example, $(1,2,2)$ and $(1,2,3,2)$ are not regular, while $(1,2,1)$ and $(1,2,3,1)$ are regular.
Proposition.
$\ $ a) $\ \phi a$ is regular for any sequence $a$.
$\ $ b) $\ $If $a$ is a regular sequence, then $\phi^2 a=a$.
Solution in progress
For a sequence $f$ define
the pre-image of $f$ denoted $f^{-1}(a):=\{n\in\mathbb{N}\mid f(n)=a\}$.
a truncation of $f$ at $t$, denoted $f_{\leq t}$, is the sequence with the domain restricted to $\{n\in\mathbb{N}\mid n\leq t\}$.
Then by $f_{\leq t}^{-1}(n)$ denote $\{k\in\mathbb{N}\mid k\leq t,f(k)=f(n)\}$. Here is a new definition for $\phi$:
Definition 1: For any sequence $f$, define $\phi f(n) := \text{card }f_{\leq n}^{-1}(n) $
The following definition and conjecture describes the sequences that $\phi$ will produce:
Definition 2: A sequence $f$ with range $\mathbb{N}$ is regular if for any truncation at $t\in\mathbb{N}$, $$\text{card }f_{\leq t}^{-1}(1)\geq\text{card }f_{\leq t}^{-1}(2)\geq\text{card }f_{\leq t}^{-1}(3)\geq...$$
That is, for any truncation of the sequence $f$, the number of $1$s is $\geq$ the number of $2$s, which is $\geq$ the number of $3$s and so on, which ensures the sequence is counting properly. I am nearly certain this definition is equivalent to those in comments.
Conjecture: If $f$ is any sequence then $\phi f$ is regular, and if $f$ is regular then $\phi^2 f = f$.
Prove $\phi f$ is regular via induction on the size of truncations and using the following lemma:
Lemma 1: A sequence $f$ is regular iff for each $t\in\mathbb{N}$ the truncated sequence $f_{\leq t}$ is regular.
Proposition: For any sequence $f$, $\phi f$ is regular.
Proof: If $t=1$, $\phi f_{\leq 1}$ is the singleton sequence, $\phi f_{\leq 1}=(1)$, so it is trivially regular.
Inductive step: Assume for any $s<t$, the truncated sequence $\phi f_{\leq s}$ is regular. Now show $\phi f_{\leq t}$ is regular by showing that for any truncation the defining inequality holds. In fact, it is sufficient to demonstrate the inequality for truncation up to length $t$.