Existence of an infinite word with a predetermined asymptotic for the word complexity 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$.
 A: 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.
A: Your function $n_w$ is usually called the word complexity function. There are several works on these possible asymptotics, though the question seems quite difficult and surprisingly little is known.
Ferenczi has a survey "Complexity of sequences and dynamical systems" which gives a large list of necessary/sufficient conditions on functions to be a word complexity function. Some highlights are:

*

*Necessary conditions: $n_w$ is nondecreasing, if $n_w$ is not strictly increasing it is bounded, $n_w$ is subadditive (i.e. $n_w(j+k) \leq n_w(j) n_w(k)$)


*Sufficient conditions: one can achieve any function $an+b$ for $a, b \in \mathbb{N}$ for sufficiently large $n$, one can achieve (asymptotically) any polynomial $n^{\alpha}$, and one can achieve (asymptotically) any $\phi: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ which is increasing, unbounded, has second derivative in $[0,1]$, and has first derivative approaching $\infty$.
In particular, this last result implies that it's possible to get $n_w \sim k \log k$ (in fact the relevant theorem says you can even do this for a sequence which has the property of uniform recurrence, meaning that every subword of $w$ appears with bounded gaps within $w$).
