Binary sequences derived from differences of consecutive quadratic residues

For a prime \begin{document}$ p\ge 5 $\end{document} let \begin{document}$ q_0,q_1,\ldots,q_{(p-3)/2} $\end{document} be the quadratic residues modulo \begin{document}$ p $\end{document} in increasing order. We study two \begin{document}$ (p-3)/2 $\end{document} -periodic binary sequences \begin{document}$ (d_n) $\end{document} and \begin{document}$ (t_n) $\end{document} defined by \begin{document}$ d_n = q_n+q_{n+1}\bmod 2 $\end{document} and \begin{document}$ t_n = 1 $\end{document} if \begin{document}$ q_{n+1} = q_n+1 $\end{document} and \begin{document}$ t_n = 0 $\end{document} otherwise, \begin{document}$ n = 0,1,\ldots,(p-5)/2 $\end{document} . For both sequences we find some sufficient conditions for attaining the maximal linear complexity \begin{document}$ (p-3)/2 $\end{document} . Studying the linear complexity of \begin{document}$ (d_n) $\end{document} was motivated by heuristics of Caragiu et al. However, \begin{document}$ (d_n) $\end{document} is not balanced and we show that a period of \begin{document}$ (d_n) $\end{document} contains about \begin{document}$ 1/3 $\end{document} zeros and \begin{document}$ 2/3 $\end{document} ones if \begin{document}$ p $\end{document} is sufficiently large. In contrast, \begin{document}$ (t_n) $\end{document} is not only essentially balanced but also all longer patterns of length \begin{document}$ s $\end{document} appear essentially equally often in the vector sequence \begin{document}$ (t_n,t_{n+1},\ldots,t_{n+s-1}) $\end{document} , \begin{document}$ n = 0,1,\ldots,(p-5)/2 $\end{document} , for any fixed \begin{document}$ s $\end{document} and sufficiently large \begin{document}$ p $\end{document} .