For an infinite binary word $w$, the *word complexity* $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the word $w$. For example, for periodic sequences we have $f_w(n)=O(1)$, for Sturmian words $f_w(n)=n+1$, for the Thue-Morse word and, more generally, for automatic sequences we have $f_w(n)=\Theta(n)$, etc.

Let $p_k$ denote the $k$-th odd prime, and let $w=(w_1w_2...)$, where $w_k = (p_k-1)/2 \mod 2$. We have $w=(10110...)$. I am curious if any nontrivial bounds are known about the word complexity in this case. The Cramér model would suggest $f_w(n)=2^n$, of course.

UPDATE (Feb 9, 2015)

I started with Shiu's reference pointed out by Lucia, and found a sizable literature on sequences of primes mod $4$. Guy reports that special cases of the problem go back to Chebyshev. It seems likely that the question is open, but here are some relevant refs.

S. Knapowski and P. Turán, On prime numbers ≡1 resp. 3 mod 4 (1977).

I.Z. Ruzsa, Consecutive primes modulo 4 (2001).

R.K. Guy, Unsolved Problems in Number Theory, 2004, $\S$A4.

K. Monks, S. Peluse and L. Ye, Strings of special primes in arithmetic progressions (2013).