  Given a prime $p\ge 5$, and given $1<\kappa<p-1$, we call a sequence
$(a_n)_{n}$ in $\mathbb{F}_p$ a $\Phi_{\kappa}$-sequence if it is periodic with
period $p-1$, and if it satisfies the linear recurrence
$a_n+a_{n+1}=a_{n+\kappa}$ with $a_0=1$. Such a sequence is said to be a
complete $\Phi_{\kappa}$-sequence if in addition
$\{a_0,a_1,...,a_{p-2}\}=\{1,...,p-1\}$. For instance, every primitive root $b$
mod $p$ generates a complete $\Phi_{\kappa}$-sequence $a_n=b^n$ for some
(unique) $\kappa$. A natural question is whether every complete
$\Phi_{\kappa}$-sequence is necessarily defined by a primitive root. For
$\kappa=2$ the answer is known to be positive. In this paper we reexamine that
case and investigate the case $\kappa=3$ together with the associated cases
$\kappa=p-2$ and $\kappa=p-3$.
