Let $w$ be an infinite binary word, for example: $$1010100001 0010011000 0001001110 0101011011 \dots$$


Let $N\_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n\_w(k)$ the cardinal of $N\_w(k)$ .  

The function $n\_w$ is the word complexity of $w$. Note that $1 \le n\_w(k) \le 2^k$. 


*Question*: Is there a word $w$ with $n\_w(k) \sim p\_k$ the k-th prime number?  

If so, is there a word $w$ with $n\_w(k) = p\_k$?


*Remark*: more than an existence proof, a natural example with this property could be interesting. More generally, we can ask what are all the possible asymptotics for such a word complexity.




---


Let the finite binary word $w = 10000100101$, then: 


* $N\_w(1) = \{0 , 1 \}$
* $N\_w(2) = \{00 , 01, 10\}$
* $N\_w(3) = \{000 , 001, 010, 100, 101 \}$
* $N\_w(4) = \{0000 , 0001, 0010, 0100, 0101, 1000, 1001 \}$


It follows that $n\_w(k) = 2,3,5,7$ for $k = 1,2,3,4$.



Existence of an infinite word with a predetermined asymptotic for the word complexity
I have already mentioned in a comment that the condition $N\_w(k)=p\_k$ cannot be satisfied for all $k$, otherwise we would have $p\_{k+1}−p\_k\leq 2(p\_k−p\_{k−1})$ which is not the case (should I explain the necessity of this condition?). Moreover, it *should* be at least true that there are infinitely many $k$ violating this inequality.


On the other hand, the required growth rate is possible.


Let us start with a general construction. Assume that $a\_1,a\_2,\dots$ is an increasing sequence such that the sequence $d\_i=a\_{i+1}-a\_i$ is also strictly increasing. Let $w$ be the word where ones are placed exactly on the positions numbered by the $a\_i$.


Take any $n$; find the largest $k$ with $d\_k<n-1$. Then each of the first $a\_k$ subwords of length $n$ contains at least two ones and hence its position in $w$ is uniquely determined by the gap between these ones. All the next $n$-subwords contain at most one 1, and there are $n+1$ of them. Thus $N\_w(n)=a\_k+n+1$. Notice here that if the monotonicity arises only eventually, this changes $N\_w(n)$ by at most a constant, thus it does not affect its grpwth rate.


Now we need to specify this construction in order to get $N\_w(n)\sim n\ln n$. Set $a\_k=[e^{\sqrt{2k}}]$; Then the sequences $(a\_k)$ and $(d\_k)$ are eventually monotone, and $d\_{k+1}/d\_k\to 1$ as $k\to \infty$. Next, 
$$
 d\_k=a\_{k+1}-a\_k\sim e^{\sqrt{2k}}(e^{\sqrt{2(k+1)}-\sqrt{2k}}-1)
 \sim \frac{e^{\sqrt{2k}}}{\sqrt{2k}}\sim \frac{a\_k}{\sqrt{2k}}.
$$
Thus
$$
 N\_w(d\_k+2)=a\_k+d\_k+3\sim a\_k\sim d\_k\sqrt{2k}\sim d\_k\ln d\_k;
$$
due to the monotonicity of $N\_w$ and the fact that $d\_{k+1}/d\_k\to 1$, we obtain $N\_w(n)\sim n\ln n$, as required.


**REMARKS.** How to find this strange form of $a\_k$? Setting $a\_k=e^{f(k)}$, we obtain that we need $f(k)(e^{f(k+1)-f(k)}-1)\sim 1$. Replacing $f(k+1)-f(k)$ by $f'(k)$, we get $e^{f'}-1=1/f$, or $f'=\ln(1+1/f)\sim 1/f$. Thus $f(k)\sim \sqrt{2k}$.


We have used the properties that $d\_k$ increases, that $d\_k=o(a\_k)$ (in the last estimate), and that $d\_{k+1}/d\_k\to 1$. This shows the conditions within which this method works.


