If we want to compare the repetitiveness of two finite words, it looks reasonable, first of all, to consider more repetitive the word repeating *more times* one of its factors, and secondarily to consider more repetitive the word repeating *larger* factors. This motivates the following definitions.

Let $w\in\{0,1\}^*$ be a finite binary word. Let us say that the digit $x\in\{0,1\}$ has repetition pair $(a,b)$ for $w$, in symbols that $R_w(x)=(a,b)$, if $a$ is the largest integer such that $wx$ has a suffix of the form $v^a$, and $b$ is the length of the longest $v$ verifying $wx=uv^a$. Clearly $R_w(0)\ne R_w(1)$.

Consider now the sequence which tries to avoid as much as possible being repetitive. This sequence $b\in\{0,1\}^\omega$ is defined as follows: $b_1=0$ and, for every $n>1$, $b_n=0$ if $R_{b_1,\dots,b_{n-1}}(0)<R_{b_1,\dots,b_{n-1}}(1)$ (where the pairs are ordered lexicographically), $b_n=1$ otherwise. This yields: $$b=0,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1,0,\dotsc.$$

Fact: the sequence is not eventually periodic.Proof: Suppose by absurd that $w$ is the shortest word such that $b=a\overline{w}$ for some (possibly empty) word $a$. You can take $M$ so large that there is no word $v$ shorter than $w$ such that $b$ has a prefix of type $a'v^M$. Suppose that at step $N=|a|+M|w|$ you chose, say, $b_N=0$ to get the prefix $aw^{M}$. This means that, by picking $b_N=1$, you would have had another suffix $s$ repeating at least $M$ times. Then by hypothesis $|s|<|w|$, but if $M>> |a|$, you have no room to get $M+1$ repetitions of a word longer than $w$.

Some natural questions:

**Q1**: what is the asymptotic density of 0s in $b$ (if it exists)?

**Q2**: when does the first triple occur? (Maybe never?) What is the critical exponent of the sequence?

**Q3**: is the sequence recurrent (that is: every factor appears twice, hence infinitely many times)?

**Q4**: considered as the binary expansion of a point in $(0,1)$, does it produce a transcendental number?

The sequence is not yet indexed on OEIS (I think I'm going to submit it, it seems fun).

Psychological remark: like most of easily bored personalities, this sequence is a bit of a sad one. Indeed, although trying as much as possible to avoid repetitions at each step, it ends up being more repetitive than its more popular friend the Thue-Morse sequence, which "locally" pursues a completely different goal, but globally achieves less repetitiveness (critical exponent=2).

**Some further thoughts**

You can generalize the proposed construction a bit. Take $w\in\{0,1\}^*$. You can define an "easily bored" sequence with prefix $w$ as the sequence $\mathcal{B}(w)=s_1s_2\dots$ selecting $x\in\{0,1\}$ at step $n$, so as to minimize the pair $R_{ws_1\dots s_{n-1}}(x)$. Notice that, in this way, $b$ is one of the two elements (the other being simply its complement sequence) of $\mathcal{B}(\epsilon)$, where $\epsilon$ is the empty word, while every nonempty finite word $w$ is associated to a unique sequence $\mathcal{B}(w)$, so that we can define the map: $$\mathcal{B}:w\in\{0,1\}^+\longrightarrow \{0,1\}^\omega$$ whose properties look not trivial.

You can also go a bit further. Indeed, given an infinite binary sequence $w=w_1w_2\dots \in\{0,1\}^\omega$, you can define $\mathcal{B}(w)$ as the limit sequence (if it exists) of: $\mathcal{B}(w^1), \mathcal{B}(w^2),\dots$, where $w^k$ is the finite word $w_kw_{k-1}\dots w_1$. This yields a final question:

**Q5**: how to characterize the subset $S\subset \{0,1\}^\omega$ such that
$$\mathcal{B}:S\to \{0,1\}^\omega$$
is well defined?

Fact: the set $S$ is nonempty.Sketch of the proof: $\overline{0}\in S$. Indeed, you can check directly that the first, say, 10 digits of the sequence $\mathcal{B}(0^m)$ are fixed for every $m$, and they contain some 1s. Therefore, at each step, the process of checking backwords the repetitions to decide whether to insert 0 or 1 has to stabilize at some point, because looking further one is certain to find only zeroes. Therefore the limit sequence exists.

italicandbold`*italic* and **bold**`

; it fits better with the other text than the corresponding TeX $\textit{italic}$ and $\textbf{bold}$`$\textit{italic}$ and $\textbf{bold}$`

. I have edited accordingly. $\endgroup$ – LSpice Nov 22 '20 at 1:446more comments