Binary sequences derived from differences of consecutive quadratic residues

For a prime $ p\ge 5 $ let $ q_0,q_1,\ldots,q_{(p-3)/2} $ be the quadratic residues modulo $ p $ in increasing order. We study two $ (p-3)/2 $-periodic binary sequences $ (d_n) $ and $ (t_n) $ defined by $ d_n = q_n+q_{n+1}\bmod 2 $ and $ t_n = 1 $ if $ q_{n+1} = q_n+1 $ and $ t_n = 0 $ otherwise, $ n = 0,1,\ldots,(p-5)/2 $. For both sequences we find some sufficient conditions for attaining the maximal linear complexity $ (p-3)/2 $.

Studying the linear complexity of $ (d_n) $ was motivated by heuristics of Caragiu et al. However, $ (d_n) $ is not balanced and we show that a period of $ (d_n) $ contains about $ 1/3 $ zeros and $ 2/3 $ ones if $ p $ is sufficiently large. In contrast, $ (t_n) $ is not only essentially balanced but also all longer patterns of length $ s $ appear essentially equally often in the vector sequence $ (t_n,t_{n+1},\ldots,t_{n+s-1}) $, $ n = 0,1,\ldots,(p-5)/2 $, for any fixed $ s $ and sufficiently large $ p $.