Fix some odd prime $p$, and let $T$ be the smallest positive integer such that $p \mid 2^{T}-1$; in other words, $T$ is the multiplicative order of 2 modulo $p$. Consider any $p$-sequence $\left(x_{n}\right)=\left(x_{0}, x_{1}, x_{2}, \ldots\right)$. Obviously, $x_{n+1} \equiv 2 x_{n}(\bmod p)$ and therefore $x_{n} \equiv 2^{n} x_{0}(\bmod p)$. This yields $x_{n+T} \equiv x_{n}(\bmod p)$ and therefore $d\left(x_{n+T}\right)=d\left(x_{n}\right)$ for all $n \geqslant 0$. It follows that the sum $d\left(x_{n}\right)+d\left(x_{n+1}\right)+\ldots+d\left(x_{n+T-1}\right)$ does not depend on $n$ and is thus a function of $x_{0}$ (and $p$) only; we shall denote this sum by $S_{p}\left(x_{0}\right)$, and extend the function $S_{p}(\cdot)$ to all (not necessarily positive) integers. Therefore, we have $x_{n+k T}=x_{n}+k S_{p}\left(x_{0}\right)$ for all positive integers $n$ and $k$. Clearly, $S_{p}\left(x_{0}\right)=S_{p}\left(2^{t} x_{0}\right)$ for every integer $t \geqslant 0$. In both parts, we use the notation
$$S_{p}^{+}=S_{p}(1)=\sum_{i=0}^{T-1} d_{p}\left(2^{i}\right) \quad \text { and } \quad S_{p}^{-}=S_{p}(-1)=\sum_{i=0}^{T-1} d_{p}\left(p-2^{i}\right)$$
(a) Let $q>3$ be a prime and $p$ a prime divisor of $2^{q}+1$ that is greater than 3. We will show that $p$ is suitable for part (a). Notice that $9 \nmid 2^{q}+1$, so that such a $p$ exists. Moreover, for any two odd primes $q$ and $a_{0}=p-1$, $a_{1}=p+2b_{0}+k S_{p}^{+}=b_{k \cdot 2 q} \quad \text { and } \quad a_{k \cdot 2 q+1}=a_{1}+k S_{p}^{+}S_{p}\left(y_{0}\right)$ but $x_{0}y_{n}$ for every $n \geqslant q+q \cdot \max \left\{y_{r}-x_{r}: r=0,1, \ldots, q-1\right\}$. Now, since $x_{0}S_{p}^{-}$, then we can put $x_{0}=1$ and $y_{0}=p-1$. Otherwise, if $S_{p}^{+}<S_{p}^{-}$, then we put $x_{0}=p-1$ and $y_{0}=p+1$.

This page is intentionally left blank