Binary sequences derived from differences of consecutive quadratic residues

For a prime $p\ge 5$ let $q_0,q_1,\dots ,q_{(p-3)\mathrm{/}2}$ be the quadratic residues modulo $p$ in increasing order. We study two $(p-3)\mathrm{/}2$-periodic binary sequences $(d_n)$ and $(t_n)$ defined by $d_n=q_n+q_{n+1}2$ and $t_n=1$ if $q_{n+1}=q_n+1$ and $t_n=0$ otherwise, $n=0,1,\dots ,(p-5)\mathrm{/}2$. For both sequences we find some sufficient conditions for attaining the maximal linear complexity $(p-3)\mathrm{/}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\mathrm{/}3$ zeros and $2\mathrm{/}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},\dots ,t_{n+s-1})$, $n=0,1,\dots ,(p-5)\mathrm{/}2$, for any fixed $s$ and sufficiently large $p$.