Given an integer $n \geq 1$, let $d_n : \mathbb{N}_{\geq 1} \to \{0,1\}$ be the coloring of the positive integers defined by $d_n(x) = 1$ if $x \mathbin{|} n$ and $d_n(x) = 0$ otherwise. In other words, factors of $n$ are colored with $1$ and all other numbers with $0$. In particular, there are a finite number of $1$s.
Given a binary word $w = w(0) w(1) \cdots w(m-1) \in \{0,1\}^m$ of some finite length $m \geq 1$, we say it occurs in $d_n$ if there exists $k \geq 1$ such that for all $0 \leq i < m$, $d_n(k+i) = w(i)$. For example, $w = 0110$ occurs in $d_{20} = 1101100001000000000100\cdots$ with $k = 3$. I'm interested in the minimal $n$ for which a given $w$ occurs in $d_n$. Let's denote it by $N(w)$.
My questions are the following:
- What is the growth rate of $\max \{ N(w) \;|\; w \in \{0,1\}^m \}$ in terms of $m$?
- What is the growth rate of the average $2^{-m} \sum_{w \in \{0,1\}^m} N(w)$ in terms of $m$?
For the first question, I can prove the following upper and lower bounds. Neither is likely to be optimal since number theory is not my strong point.
Proposition 1. For $m \geq 1$ and $w \in \{0,1\}^m$, we have $N(w) < ((C(m) \cdot 2 m \log 2 m)^m + m)^m$ with $C(m) \to 1$ as $m \to \infty$. In particular, $N(w)$ always exists.
Proof. Denote the $i$th prime by $p_i$. By the Chinese Remainder Theorem, there exists $k \leq \prod_{i = 0}^{m-1} p_{m+i}$ with $k \equiv -i \bmod p_{m+i}$ for each $0 \leq i < m$. Let $n = \prod_{w(i) = 1} (k+i)$. Then $w$ occurs in $d_n$ with this choice of $k$, as each $k+i$ is divisible by $p_{m+i}$ but not $p_{m+j}$ for any $0 \leq j < m$, $j \neq i$. The Prime Number Theorem implies $p_{m+i} < p_{2 m} = C(m) \cdot 2 m \log 2 m$ with $C(m) \to 1$. Then $n \leq (k+m)^m < ((C(m) \cdot 2 m \log 2 m)^m + m)^m$. QED.
Proposition 2. For $w = 0 1^{m-1}$, we have $N(w) \geq \binom{2 m}{m}/2$.
Proof. Suppose that $w$ occurs in $d_n$ at $k \geq 1$. Of course, $k = 1$ is impossible since $w(0) = 0$ and $d_n(1) = 1$ for every $n$, so we must have $k > 1$. If $k < m$, then $2k < k+m$, and hence $d_n(2k) = w(k-1) = 1$, so that $2k$ divides $n$. But then $k$ divides $n$, contradicting $d_n(k) = w(0) = 0$. Hence $k \geq m$. Now, $n$ is divisible by $k+i$ for each $1 \leq i < m$ and hence their lowest common multiple. We have $$\mathrm{lcm}(k+1, k+2, \ldots, k+m-1) \geq \frac{\prod_{i=1}^{m-1} (k+i)}{(m-1)!} \geq \frac{(2m-1)!}{m!(m-1)!} = \frac{1}{2} \binom{2 m}{m}.$$ The first inequality follows from Theorem 2.3 of [1]. QED.
[1]: Bakir Farhi: Minorations non triviales du plus petit commun multiple de certaines suites finies d'entiers. Comptes Rendus Mathematique 341(8), 2005, pp. 469-474. https://doi.org/10.1016/j.crma.2005.09.019
