, 2021

Answer: Yes, for both parts.

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 $(x_n) = (x_0, x_1, x_2, \dots)$. Obviously, $x_{n+1} \equiv 2x_n \pmod p$ and therefore $x_n \equiv 2^n x_0 \pmod p$. This yields $x_{n+T} \equiv x_n \pmod p$ and therefore $d(x_{n+T}) = d(x_n)$ for all $n \ge 0$. It follows that the sum $d(x_n)+d(x_{n+1})+\dots+d(x_{n+T-1})$ does not depend on $n$ and is thus a function of $x_0$ and $p$ only; we shall denote this sum by $S_p(x_0)$, and extend the function $S_p(\cdot)$ to all (not necessarily positive) integers. Therefore, we have $x_{n+kT} = x_n + kS_p(x_0)$ for all positive integers $n$ and $k$. Clearly, $S_p(x_0) = S_p(2^t x_0)$ for every integer $t \ge 0$.

In both parts, we use the notation
$$S_p^+ = S_p(1) = \sum_{i=0}^{T-1} d_p(2^i) \text{ and } S_p^- = S_p(-1) = \sum_{i=0}^{T-1} d_p(p - 2^i)$$

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 < r$ we have $\gcd(2^q + 1, 2^r + 1) = 2^{\gcd(q,r)} + 1 = 3$, thus there exist infinitely many such primes $p$.

For the chosen $p$, we have $T = 2q$. Since $2^q \equiv -1 \pmod p$, we have $S_p^+ = S_p^-$. Now consider the $p$-sequences $(a_n)$ and $(b_n)$ with $a_0 = p+1$ and $b_0 = p-1$; we claim that these sequences satisfy the required conditions. We have $a_0 > b_0$ and

$$a_{k \cdot 2q} = a_0 + kS_p^+ > b_0 + kS_p^+ = b_{k \cdot 2q} \text{ and } a_{k \cdot 2q+1} = a_1 + kS_p^+ < b_1 + kS_p^+ = b_{k \cdot 2q+1}$$
for all $k = 0, 1, \dots$, as desired.

b.
Let $q$ be an odd prime and $p$ a prime divisor of $2^q - 1$; thus we have $T = q$. We will show that $p$ is suitable for part (b). Notice that the numbers of the form $2^q - 1$ are pairwise coprime (since $\gcd(2^q - 1, 2^r - 1) = 2^{\gcd(q,r)} - 1 = 1$ for any two distinct primes $q$ and $r$), thus there exist infinitely many such primes $p$. Notice that $d_p(x) + d_p(p-x) = p$ for all $x$ with $p \nmid x$, so that the sum $S_p^+ + S_p^- = pq$ is odd, which yields $S_p^+ = S_p(1) \neq S_p(-1) = S_p^-$. Assume that $(x_n)$ and $(y_n)$ are two $p$-sequences with $S_p(x_0) > S_p(y_0)$ but $x_0 < y_0$. The first condition yields that
$$x_{M_{q+r}} - y_{M_{q+r}} = (x_r - y_r) + M(S_p(x_0) - S_p(y_0)) \geq (x_r - y_r) + M$$
for all nonnegative integers $M$ and every $r = 0, 1, \dots, q-1$. Thus, we have $x_n > y_n$ for every $n \ge q + q \cdot \max\{y_r - x_r : r = 0, 1, \dots, q-1\}$. Now, since $x_0 < y_0$, there exists the target $n_0$ with $x_{n_0} < y_{n_0}$. In this case the $p$-sequences $a_n = x_{n-n_0}$ and $b_n = y_{n-n_0}$ possess the desired property (notice here that $x_n \neq y_n$ for all $n \ge 0$, as otherwise we would have $S_p(x_0) = S_p(x_n) = S_p(y_n) = S_p(y_0)$).

It remains to find $p$-sequences $(x_n)$ and $(y_n)$ satisfying the two conditions. Recall that $S_p^+ \neq S_p^-$. Now if $S_p^+ > 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$.