Throughout the solution, let $d$ denote the order of $p$ modulo $2$, and let $l=\frac{p-1}{d}.$ We first note that any $p$-sequence is periodic modulo $p$, with period being exactly $d$, since $a_k \equiv 2^ka_0 \pmod{p}$. For part a), let $p>3$ be a prime such that $2^n \equiv -1 \pmod{p}$ for some positive integer $n$ (for example, any prime such that $2$ is not a quadratic residue works), and consider the $p$-sequences $(a_n)$ and $(b_n)$ starting with $p-1$ and $p+1$. We have $a_0<b_0$ and $2p-2=a_1>b_1=p+2$. On the other hand, note that $$d_p(a_0)+d_p(a_1)+\ldots+d_p(a_{d-1})=d_p(b_0)+d_p(b_1)+\ldots+d_p(b_{d-1})=d_p(1)+d_p(2)+\ldots+d_p(2^{d-1}).$$Therefore, $a_{d+j}-a_j=b_{d+j}-b_j$ for any $k,j \geq 0$, since those differences are equal to the sum $d_p(b_0)+d_p(b_1)+\ldots+d_p(b_{d-1})=d_p(1)+d_p(2)+\ldots+d_p(2^{d-1})$. Then $a_{kd}<b_{kd}$ and $a_{kd+1}>b_{kd+1}$ for any $k\geq 0$, which proves the claim. For part b), let $p$ be a prime such that $d$ is odd (for example, any prime dividing $2^q-1$ for some prime number $q>2$). Then $\frac{p-1}{d}$. Let $u_1, \ldots, u_l$ be elements of $(\mathbb Z/p\mathbb Z)^{\times}$ such that the numbers $(u_i2^j)_{i\leq l, \ j\leq d}$ cover the entirety of $(\mathbb Z/p\mathbb Z)^{\times}$. Now, if the sums $\sum_{j=1}^d d_p(u_i2^j)$ are all equal to the same number $S$ for any $i \leq l$, we have an equality $$lS=1+2+\ldots+p-1=\frac{p(p-1)}{2}.$$But then $l$ divides $\frac{p-1}{2}$, but this is equivalent to $2$ dividing $d$ which is a contradiction. Therefore, there are indices $i$ and $k$ such that $\sum_{j=1}^d d_p(u_i2^j)>\sum_{j=1}^d d_p(u_k2^j)$. Now consider the $p$-sequences $(a_n)$, $(b_n)$ starting with $u_i$ and $p+u_k$ respectively (note that $a_0<b_0$ and that $a_n$ and $b_n$ are always distinct modulo $p$). Then, for any $r<d$ and any $k>0$, $a_{kd+r}=k\sum_{j=1}^d d_p(u_i2^j)+a_r$ and $b_{kd+r}=k\sum_{j=1}^d d_p(u_k2^j)+b_r$. For any $r$, the function $k \mapsto a_{kd+r}-b_{kd+r}$ is strictly increasing. Therefore, $a_{n}>b_{n}$ for all but finitely many $n$. Now take the greatest $m\geq 0$ such that $a_m<b_m$. Then the sequences $(a_{m+n})_n$ and $(b_{m+n})_n$ satisfy the condition.

Solved with dantaxyz. (a) Let $m$ be the order of $2\pmod{p}$. Then for any $p$-dop $\mathbf{x}$, note that $\{x_{\ell+1} \% p,\ldots,x_{\ell+m} \% p\}$ is the same set over all $\ell\ge 0$, since $x_{n+1} \equiv 2x_n \pmod{p}$. Hence $x_{\ell+m}-x_\ell$ is a constant for all $\ell\ge 0$. Call this constant $C_a$ for $\mathbf{a}$ and $C_b$ for $\mathbf{b}$. The idea is to use $(a_0,b_0)=(p-1,p+1)$, since then $a_0<b_0$, and $(a_1,b_1)=(2p-2, p+2)$, which satisfies $a_1>b_1$. (The intuition is that $a_0$ is initially smaller, but it's jump is much larger than $b_0$'s.) If we can show that $C_a=C_b$ for infinitely many $p$, then $a_{km}=(p-1)+C_ak$ and $b_{km}=(p+1)+C_bk$, so $a_{km}<b_{km}$ and $a_{km+1}>b_{km+1}$ for all $k\ge 0$, finishing. Consider the set $(b_0 \%p, b_1\%p,\ldots,b_{m-1}\%p)$. The idea is to force one of these to be $-1\pmod{p}$, since if $b_k \equiv p-1 \pmod{p}$ say, then the set $\{b_k \% p, b_{k+1} \%p ,\ldots,b_{k+m-1}\%p\}$ would be equal to $\{a_0\%p,\ldots,a_{m-1}\%p\}$, which means $b_{k+m}-b_k = a_{m}-a_0$. But the former is equal to $C_b$, and the latter $C_a$, so we would have $C_b=C_a$, as desired. So we want $b_k\equiv p-1 \pmod{p}$ for some $0\le k\le m-1$. Since $b_k\equiv 2^kb_0 = 2^k(p+1) \equiv 2^k \pmod{p}$, we want infinitely many $p$ satisfying $p\mid 2^k+1$ for some $k$. By Zsigmondy's Theorem, we are guaranteed that the sequence $(2^k+1)_{k\ge 0}$ has a new prime factor at each increment, so we are done. (b) Start with $(a_0,b_0)=(x,y)$. Note that $a_{km+r}=a_r+kC_a$ and $b_{km+r}=b_r+kC_b$. Assume we have $C_a < C_b$ for some $(a_0,b_0)=(x,y)$. Indeed, for some $S$, we will have $a_s < b_s$ for all $s\ge S$, since the linear growth rate of one of $\mathbf{a}$ is less than that of $\mathbf{b}$. Consider the minimal such $S$. Simply cut off the first $S-1$ elements of $\mathbf{a}$ and $\mathbf{b}$, and then by definition we are done. The only snag is if $x \le y$; then it is possible that no $i$ satisfies $a_i<b_i$ even before truncation. To guarantee this from not happening, simply start with $(a_0,b_0)=(p+x,y)$ if $x\le y$; then we definitely have at least one $i$ ($i=0$) for which $a_i<b_i$ before truncation. Let $S(z)=\{ z\%p,2z\%p,\ldots,2^{m-1}z\%p\}$. Note that if $(a_0,b_0)=(x,y)$, then $C_a=\sum S(x)$ and $C_b=\sum S(y)$. We showed above that if $C_a<C_b$ for some $x,y$, then we can finish. So assume for the sake of contradiction that $\sum S(x)=\sum S(y)$ for all $x,y$. Draw dots at $0,1,\ldots,p-1$, and start with an uncolored number $z$, and color with the same new color $2^iz\%p$ for each $i\ge 0$. We are assuming that the sum of numbers with each color is the same. This implies that the number of colors divides $0+1+\cdots+(p-1)=\tfrac{p(p-1)}{2}$. The number of colors is $\tfrac{p-1}{m}$, so we have \[ \frac{p-1}{m} \mid \frac{p(p-1)}{2} \iff 2(p-1) \mid p(p-1)m \iff 2 \mid pm. \]Therefore, $m$ is even. However, we can force infinitely many primes $p$ which have the order of $2\pmod{p}$ being odd by Kobayashi (there are lower-powered ways to prove this, too). So for these primes, we have a contradiction, finishing.

Here's the solution I submitted for part (b) -- the one given on my TST. The answer is Yes. We claim that there are infinitely many primes $p \equiv 7 \pmod{8}$ satisfying the condition. First of all, we define a chain of residues $\{ r_1, r_2, \dots, r_k \}$ such that $r_{i + 1} \equiv 2 r_i \pmod{p}$ and $r_{k + 1} = r_1$. Claim 01. If $p \equiv 7 \pmod{8}$, we can divide all $p - 1$ residues into a bunch of chains. Then, there exists two chain of odd length. Proof. We first claim that $a$ and $p - a$ won't lie on the same chain for all $a \in [1,p - 1]$. Suppose otherwise, by definition, \[ 2^{\ell} a \equiv -a \pmod{p} \implies 2^{\ell} + 1 \equiv 0 \pmod{p} \]However, $p \equiv 3 \pmod{4}$, which implies $\ell$ being odd. However, this implies $-2$ is a QR modulo $p$, which is not the case since $p \equiv 7 \pmod{8}$. Hence, we can divide the residues into $2$ large groups of same size such that if $a \in A$, then $-a \in B$. It's immediate to see that $|A| = |B| = \frac{p - 1}{2}$, which is an odd number. Thus, if we divide each members of $A$ into chains, since $|A|$ is odd, there must exists an odd length chain. In fact, if $x$ is a member of odd length chain, by our previous argument, $p - x$ is also an element of an odd length chain. Now, call both odd length chains as chain $A$ and $B$, from which we can pick such that $|A| = |B|$ by taking chain $B$ to be the chain containing $-a$ for all $a \in A$. We now claim that \[ \sum_{r \in A} r \not= \sum_{j \in B} j \]Suppose otherwise, that they have the same sum, then we could pair things up, and we get \[ \sum_{r \in A} r + \sum_{j \in B} j = p|A| \equiv 1 \pmod{2} \]Therefore, they must have a different sum. Call the chain with the larger sum as $A$ and the smaller sum as $B$. Let $A = \{ j_1, j_2, \dots, j_n \}$ and $B = \{ r_1, r_2, \dots, r_n \}$. Take the maximal element $b$ in $B$, and minimal element $a$ in $A$. Take the smallest $k \in \mathbb{N}$ such that $b + kp > a$. Take these numbers as our $a_0 = a$ and $b_0 = b + kp$. We claim that $a_i < b_i$ happens only for finitely many $i \in \mathbb{N}$. Suppose otherwise, since we have $|A| = |B|$ number of residues, eventually the sum of both sides will repeat (periodic), which forces $a_n \equiv a_0 \pmod{p}$ and $b_n \equiv b_0 \pmod{p}$ where $n = |A|$. Now, among \[ a_0 - b_0, a_1 - b_1, \dots, a_{n - 1} - b_{n - 1} \]Take $\Delta$ as minimal value among these numbers, which must exists since $n$ is finite. Now, since $\sum_{i = 1}^n j_i > \sum_{i = 1}^n r_i$ by assumption, take large value $X$ such that \[ X \left( \sum_{i = 1}^n j_i - \sum_{i = 1}^n r_i \right) + \Delta > 0 \]Now, notice that \[ a_{mn + k} - b_{mn + k} = (a_k - b_k) + \left( \sum_{i = 1}^n j_i - \sum_{i = 1}^n r_i \right) m \]Hence, for all large index $i$, we will have $a_i - b_i > 0$. Therefore, we have proved that $a_i < b_i$ happens finitely often. Now, take largest $j \in \mathbb{N}$ such that $a_j < b_j$. This must happen as $a_i < b_i$ happens finitely often. We will thus redefine $a_j$ as our new $a_0$ and $b_j$ as our new $b_0$. However, by our choice of $j$, we will have $a_i > b_i$ for all $i \ge 1$, and we are done since there are infinitely many primes $p \equiv 7 \pmod{8}$ by Dirichlet's Theorem.

It is easy to see that $a_n\equiv 2^na_0\pmod p$. Therefore, $d(a_n)$ is periodic with period $d$, where $d$ is the order of $2$ modulo $n$. Therefore, since $d|p-1$, $$a_{n+p-1}-a_n=\sum_{i=0}^{p-1}d(2^ia_0)\hspace{20pt}(1)$$is a constant. We define this constant to be the difference of a $p$-sequence. (a) Pick a prime $p$ such that $p\equiv \pm 3\pmod 8$. Claim. The difference of every $p$-sequence is the same. Proof. Indeed, $$2^{\frac{p-1}{2}}\equiv \left(\frac{2}{p}\right)=-1\pmod p$$Therefore, $$2^ia_0+2^{i+\frac{p-1}{2}}a_0\equiv 0\pmod p$$hence $$\sum_{i=0}^{p-1}d(2^ia_0)=\sum_{i=0}^{\frac{p-3}{2}}d(2^ia_0)+d(2^{i+\frac{p-1}{2}})=\frac{p(p-1)}{2}$$which is a constant not depending on $a_0$. $\blacksquare$ Therefore, given two p-sequence $a_0,a_1,...,a_n,...$ and $b_0,b_1,...,b_n,...$ the sequence $a_n-b_n$ is also periodic. Therefore it suffices to pick $a_0$ and $b_0$ such that $a_0<b_0$ and $a_1>b_1$. Indeed, we can just pick $a_0=p-1$ and $b_0=p+1$ so we are done. (b) Pick a prime $p$ such that $p\equiv -1\pmod 8$, then Claim. The difference of the $p$-sequence with starting term $1$ and $-1$ is different. Proof. Indeed, $$2^{\frac{p-1}{2}}\equiv \left(\frac{2}{p}\right)=1\pmod p$$Meanwhile, $-1$ is not a quadratic residue mod $p$ so the two sequenes are disjoint. Let the two sequences be $\{a_n\},\{b_n\}$ Therefore, letting $e$ be the order of $2$ modulo $p$, we have that $$a_i-a{i-1}=\begin{cases}d(2^i)-d^(2^{i-1})&\text{ if }d(2^{i-1})\leq\frac{p-1}{2}\\ d(2^i)-d^(2^{i-1})+ap\end{cases}\hspace{20pt}(2)$$Where $a$ be the number of integers in the sequence $d(1),d(2),...,d(2^{e-1})$ which are at most $\frac{p-1}{2}$. Similarly, let $b$ be the number of integers in the sequence $d(-1),d(-2),...,d(-2^{e-1})$ which are at most $\frac{p-1}{2}$. Notice that $a+b=d|\frac{p-1}{2}$. Hence $a+b$ is odd which in particular implies $a\neq b$. Therefore, (2) implies their difference are distinct. $\blacksquare$ Now suppose the sequence starting with $-1$ has the larger difference, called it $\{a_n\}$ and the sequence starting with $1$ be $\{b_n\}$. Then obviously $a_n>b_n$ for sufficiently large $n$ and $a_0<b_0$. Let $i$ be the largest indice such that $a_i<b_i$ then pick the $p$-sequences starting with them then we are done. In the other case just replace $(-1,1)$ by $(1,p-1)$.

$\textbf{EDIT:}$

$\color{green} \rule{3cm}{2pt}$ $\color{green} \clubsuit$ $\boxed{\textbf{Definition.}}$ $\color{green} \clubsuit$ $\color{green} \rule{3cm}{2pt}$ Let a prime $p$ to be $\textit{excellent}$ if 2's order modulo $p$ is odd. In this section we will prove that there exists infinitely many excellent primes; and later we will prove that any excellent prime will have two $p$-sequences prescribed in the problem condition. $\color{green} \rule{25cm}{0.3pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Construction.}}$ $\color{green} \spadesuit$ Let we have constructed excellent primes $r_1,r_2,\ldots,r_k$. Pick a prime $q$ greater than $\text{max}(r_1,\ldots,r_k)$ and pick \[ r_{k+1}\mid 2^q-1 \]By a well-known Lemma, $r_{k+1} \equiv 1 \pmod q$; so $r_{k+1} > r_1,r_2,\ldots,r_k$. Since $q$ is a prime, $\text{ord}_2(r_{k+1}) \in \{1,q\}$. As $r_{k+1}$ obviously does not divide $2^1-1$, its order must be exactly $q$, a prime which must be odd. We are done. Now we follow this with a series of Claims. $\color{red} \rule{8.25cm}{2pt}$ $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{Claim 1: Easy but rich and fundamental.}}$ $\color{red} \clubsuit$ $\color{red} \rule{8.25cm}{2pt}$ For each sequence $\{a_i\} = (a_0,a_1,a_2,\ldots,)$ we define $a_i$'s $\textit{delta set}$ to be $\Delta(\{a_i\}) = (a_1-a_0,a_2-a_1,\ldots,)$. Following from that, define $\Delta_n$ for individual terms, which is $a_{n+1}-a_n$. We claim that The delta set of any $p$-sequence is periodic modulo $d$, where $d = \text{ord}_2(p)$, $\Delta_i \equiv a_i \pmod p$, and $\{\Delta_i, \Delta_{i+1},\ldots,\Delta_j\} \equiv \{a_i,\ldots,a_j\} \pmod p$ (reduced to be the smallest possible natural) for any $i,j$. $\color{red} \rule{25cm}{0.3pt}$ $\color{red} \spadesuit$ $ \color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$ The first one is inferred by noticing $a_{i+1}\equiv 2 a_i \pmod p$; that means $a_{j} \equiv a_i \pmod p$ iff $2^{j-i} \equiv 1 \pmod p$. That is achievable iff $d \mid j-i$; i.e. if the sequence $\{a_i\}$ is periodic with period $d$. We now move on to the second one first. This is very direct, as $\Delta_i = a_{i+1} - a_i = d_p(a_i) \equiv a_i \pmod p$. From now on, refer $\Delta_i$ as the simple $d_i$; as we are only considering excellent primes $p$ (so there's no need for $p$ to vary). By that, since $\{a_i\} \pmod p$ is periodic with period $d$, so is $\{\Delta_i\}$. The third one is also direct, as we know $d_i \equiv a_i, d_{i+1} \equiv a_{i+1},\ldots, d_j \equiv a_j$; so those sets are exactly equal without needing to re-order the elements. We are done. $\blacksquare$ $\color{cyan} \rule{2.6cm}{2pt}$ $\color{cyan} \clubsuit$ $ \boxed{\textbf{Claim 2.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{2.6cm}{2pt}$ For each sequence $\{a_i\}$, we define its $\textit{characteristic}$ to be the sum of its $d$ deltas. Then, each sequence's characteristic is divisible by $p$. $\color{cyan} \rule{25cm}{0.3pt}$ $\color{cyan} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{cyan} \spadesuit$ The characteristic is in the form of \[ (a_0 \ \text{mod} \ p) + (2a_0 \ \text{mod} \ p)+\ldots+(2^{d-1}a_0 \ \text{mod} \ p) = (2^d-1)a_0-kp \equiv 0 \pmod p \]where $kp$ is the total substractions of the $``2^ia_0''$s for it to reach a number less than $p$. $\color{cyan} \rule{2.6cm}{2pt}$ $\color{cyan} \clubsuit$ $ \boxed{\textbf{Claim 3.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{2.6cm}{2pt}$ Define a sequence's $\textit{class}$ to be the set of its $d$ deltas. Then, each there are exactly $\dfrac{p-1}{d}$ different $\textit{classes}$; and there exists two sequence with different characteristics (of course, with two different classes/delta-families). $\color{cyan} \rule{25cm}{0.3pt}$ $\color{cyan} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{cyan} \spadesuit$ For the first statement, we construct the $\dfrac{p-1}{d}$ classes step-by-step. Let we have formed $C_1 = \{a_1,2a_1,\ldots,2^{d-1}a_1\}$ up to $C_k = \{a_k,\ldots,2^{d-1}k\}$ with all of the $dk$ terms different --- and we would like to construct a $C_{k+1}$ if $k < \dfrac{p-1}{d}$. If so, we know that $dk < p-1$, so there is a term $A$ which is not among the $dk$ terms already included in the $k$ classes. Now form a $p$-sequence with $a_0 = A$, and by the points of $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{Claim 1}}$ $\color{red} \clubsuit$ we know that the delta-set of $\{a_i\}$ is exactly $\{A,2A,\ldots,2^{d-1}A\}$. Here we utilize the full force of the (quite) strong third point of $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{Claim 1}}$ $\color{red} \clubsuit$. If an element of $\{A,2A,\ldots,2^{d-1}A\}$; say $2^iA$, is an element of some $C_m$, namely $2^ja_m$, we can derive a contradiction. While simple working modulo $p$ yields $A \equiv 2^{j-i}a_m$, thereby forming a contradiction, a fancier way to phrase (and motivate) this is by

The second statement is a little bit technical (where the first is strictly structural) --- where if all $\dfrac{p-1}{d}$ sequences have equal sum, we would have \[ \dfrac{p-1}{d} \mid \dfrac{p(p-1)}{2} \Rightarrow \dfrac{1}{d} \mid \dfrac{p}{2} \]which is a blatant lie. $\blacksquare$ $\blacksquare$

$\color{magenta} \rule{9.8cm}{2pt}$ $\color{magenta} \diamondsuit$ $ \boxed{\textbf{Extreme Minimality and Strict Sequences Finish.}}$ $\color{magenta} \diamondsuit$ $\color{magenta} \rule{9.8cm}{2pt}$ Pick two sequences \[ \{s_i\} = (s_1,s_2,\ldots,s_d,s_{d+1} = s_1+C_1,\ldots) \]and $\{t_i\}$ that satisfies the second condition in $\color{cyan} \clubsuit$ $ \boxed{\textbf{Claim 3}}$ $\color{cyan} \clubsuit$. Let $\{s_i\}$ and $\{t_i\}$ have characteristics $C_1$ and $C_2$, where $C_1 < C_2$. $\color{green} \rule{25cm}{0.3pt}$ First (unlike my actual work on the test), we will first prove that $t_i \ne s_j \pmod p$ for every $i,j$. However, assuming that the characteristics of those two sets are different, their class also must be different, implying the conclusion. Extra: so, whenever constructing a subsequence of these two sets, we can be assured that $a_n \ne b_n$, shrinking the strong $a_0 < b_0$ and $a_i > b_i \forall i \geq 1$ in the problem condition to be a weaker version: $a_0 < b_0$ and $a_i$ not smaller than $b_i, \ \forall i \geq 1$. $\color{green} \rule{25cm}{0.3pt}$ With that said, we proceed to the actual argument:

For each $t_i$, assign a $s_{k_i}$ to it --- where that term is the smallest (or earliest) in the sequence $\{s_i\}$ so that it's greater than $t_i$. This term exists (for obvious reasons) and unique (since $\{s_i\}$ is strictly increasing.) Now, let the number $k_i-i$ to be $f(i) \ \forall i \geq 1$. Out of all $i$, call the ones with the least value to be $\textit{good}$, and call the latest good one to be $\textit{special}$. We claim that all good indices must be less than $d$. To that end, we prove that $f(i+d) > f(i)$. Note that since $p \mid C_1$ and $p \mid C_2$, $C_2 - C_1 \geq p$. Let $s_m < t_i < s_{m+1}$. Then, $s_{m+d} = s_m + C_1$, $t_{i+d} = t_i + C_2$ and $s_{m+1+d} = s_m + d_m + C_1$. By this alone, we can already prove that \[ t_i + C_2 \geq t_i + p +C_1 > s_m + p +C_1 > s_m+d_m+C_1 = s_{m+1}+C_1 = s_{m+1+d} \]So $f(i+d) > m+1+d-(i+d) = m+1-i$, while $f(i) = m+1-i$. So, $f(i+d) > f(i)$. So, there are finite good indices, so it makes sense to pick the largest of them $L$ to be $\textit{special}$. $\color{magenta} \rule{6.9cm}{2pt}$ $\color{magenta} \diamondsuit$ $ \boxed{\textbf{Extreme Minimality Real Finish.}}$ $\color{magenta} \diamondsuit$ $\color{magenta} \rule{6.9cm}{2pt}$ Set $a_0 = t_L$ and $b_0 = s_{k_L}$. If there exists an index $j$ so that $a_j \leq b_j$; i.e. $a_j < b_j$, then $b_j = t_{L+j}$, implying $a_j = s_{k_{L}+j}$. We will prove that $j$ is a good index (with respect to $\{s_i\}$ and $\{t_i\}$). This willl contradict $L$ being a special term, since there exists a good index after it. Now, as $f(j+L) \geq f(j)$ (since $f(j)$ is the minimum of $f(i)$ across all $i$) this creates $k_{L+j} - (L+j) \geq k_L - L$ or $k_{L+j} \geq k_L+j$. If that inequality is a non-equality, then we know that $a_j > b_j$ as by definition, $s_{k_{L+j}}$ is the smallest term in $\{s_i\}$ which exceed $a_j$ --- so $s_{k_L+j}$, which is before that term, must be smaller than $a_j$. However, if that inequality is an equality, then $f(L+j) = f(L)$. We are finally done. $\blacksquare$ $\blacksquare$ $\blacksquare$

Very beautiful problem. First, we notice that $a_n = a_{n-1} + d_p(a_{n-1}) \equiv 2a_{n-1} \equiv \cdot \cdot \cdot \equiv 2^{n}a_0 \pmod p$. Let $k$ be the order of $2$ modulo $p$ and let $S(a_0) = d_p(a_0) + d_p(a_1) + \cdot \cdot \cdot d_p(a_{k-1})$. For any integer $m$, we have that $a_{mk} = a_0 + mS(a_0)$ and $a_{mk +1} = a_1 + S(a_0)$ by the recursive relation using the identity $a_n \equiv 2^na_0 \pmod p$. Moreover, whenever $a_0 \equiv 2^tb_0 \pmod p$, we have $S(a_0) = S(b_0)$. Now,we claim that the answer for both items is Yes. Indeed, for $a)$ we just need to find $a_0 > b_0$ such that $a_1 < b_1$ and $a_0 \equiv 2^tb_0 \pmod p$ for some $t$ positive integer. We take $a_0 = p+1$, $b_0 = p-1$, then $a_1 = p+2$, $b_1 = 2p-2$ and $a_0 \equiv 2^tb_0 \pmod p \iff 2^{t-1} \equiv -1 \pmod p$, one may take $p \equiv 3$ or $5 \pmod 8$, then $2$ is not a residue so $t-1 = \frac{p-1}{2}$ fits here. Now we go to item $b)$. Notice that $a_{mk+r}-b_{mk+r}=(a_0-b_0)+m(S(a_0)-S(b_0)) + (d_p(a_{r-1}) + \cdot \cdot \cdot + d_p(a_0)) - (d_p(b_{r-1}) + \cdot \cdot \cdot + d_p(b_0))$. Hence, whenever $S(a_0) > S(b_0)$, we have $a_{mk+r}-b_{mk+r} > 0$ for sufficient large $m$. Then, just need to find $a_0,b_0$ s.t $b_0 > a_0$, $S(a_0) > S(b_0)$ then just take the subsequence up to the previous point that $a_{mk+r}-b_{mk+r} > 0$ holds for the least value of $m$. Notice that we can take $a_0 = p-1, b_0 = p+1$, since $S(a_0) + S(b_0) = pk$, if $k$ is odd then $S(a_0) \neq S(b_0)$. If $S(a_0) > S(b_0)$ we're done, just take the primes $p$ that divide the numbers of the form $2^q -1$ with $q$ being an odd prime. However, if $S(a_0) < S(b_0)$, then taking $b_0 = 2p-1$,$a_0 = p+1$ and the same primes $p$, we have the desired. Hence, we're done.

..........

I thought this was easier than N2 and N3.

(a) Let $f(i,j)=d_p(i\cdot2^j)$. Then, since $x_{n+1}\equiv2x_n\pmod p$, this means that $x_n\equiv2^nx_0\pmod p$, so $x_{n+1}=x_n+f(x_0,n)$. Let $k=\operatorname{ord}_p(2)$. Since there are infinitely many primes that are equivalent to $1$ mod $4$, this means that if $2^a<p<2^{a+1}-2$, then $a_0=2^a$ and $b_0=p+1$ works since $a_0<b_0$, $a_1=2^{a+1}>b_1=p+2$, and $a_{n+k}-a_n=\sum_{i=0}^{k-1}f(2^a,n+i)=1+2+4+\ldots+2^{k-1}$ and $b_{n+k}-b_n=\sum_{i=0}^{k-1}f(1,n+i)=1+2+4+\ldots+2^{k-1}$. Therefore, there are infinitely many $p$ that satisfy the condition. (b) Suppose that there exists $a_0$ and $b_0$ such that $\sum_{i=0}^{k-1}f(a_0,i)>\sum_{i=0}^{k-1}f(b_0,i)$ and $a_0<b_0$. Then, there exists $m$ such that $a_m<b_m$ and $a_i>b_i$ for all $i>m$, so $(a_m,a_{m+1},a_{m+2},\ldots)$ and $(b_m,b_{m+1},b_{m+2},\ldots)$ satisfy the conditions. Now, there are infinitely many $p\equiv7\pmod8$. Then, we have $\sum_{i=0}^{k-1}f(1,i)+\sum_{i=0}^{k-1}f(-1,i)=pk$. Since $2$ is a quadratic residue mod $p$ and $p\equiv3\pmod4$, this means that $\operatorname{ord}_p(2)\mid\frac{p-1}2$ is odd. Therefore, this sum is odd, so one of the terms is greater than the other. Then, we can make one of $a_0$ and $b_0$ be $1$ mod $p$ and the other one $-1$ mod $p$, and add a multiple of $p$ to make $a_0<b_0$. Then, there exists a sequence that works, so there are infinitely many $p$ that satisfy the condition.

Throughout this solution, let $m=\mathrm{ord}_p(2)$. Note that $a_{n+1} \equiv 2a_n \pmod{p}$. Further, any $p$-sequence has (minimal) period $m$. Thus, let the character of an integer $k$ be the set of $m$ mod-$p$ residues which the $p$-sequence starting with $k$ takes, and note that if two "character sets" aren't disjoint, then they're equal, because starting from a shared value, the rest of the character sets must be the same. Thus, there are $\tfrac{p-1}{m}$ unique character sets. Finally, let the height of an integer $k$ denote the value of $a_{i+m}-a_i$, where $(a_0,a_1,\ldots)$ is the $p$-sequence that has $a_0=k$ (this value is independent of $i$), and let the height of a character set be the height of one of its elements (this value is also independent of which element we select). For part (a), pick some $p$ dividing $2^k+1$ for some $k \geq 1$, of which there are infinitely many by Zsigmondy/Kobayashi/whatever. I claim selecting $a_0=p-1$ and $b_0=p+1$ works. Note that since there exists $2^k \equiv -1 \pmod{p}$, the characters of $a_0$ and $b_0$ overlap and are thus identical, hence they have equal heights. Since $a_1=2p-2>p+2=b_1$, it follows that we have $a_{im}<b_{im}$ and $a_{im+1}>b_{im+1}$ for all $i \geq 0$, done. $\blacksquare$ For part (b), pick some prime $p \equiv 7 \pmod{8}$, of which there are infinitely many by Dirichlet. We first prove the following lemma: Lemma: $m$ is odd. Proof: First note that $2$ is a quadratic residue modulo $p$, thus if $a^2 \equiv 2 \pmod{p}$ then $\mathrm{ord}_p(a)=2m$. On the other hand, if $m$ is even, then $4 \mid \mathrm{ord}_p(a) \mid p-1$, which is impossible. $\blacksquare$ With this fact, we are ready to prove the main claim. Main Claim: There exist two integers $a,b$ with different heights. Proof: Suppose otherwise. Note that the sum of all of the heights of each unique character set modulo $p$ is simply $1+2+\cdots+(p-1)=\tfrac{p(p-1)}{2}$. Since we have $\tfrac{p-1}{m}$ character sets, it follows that each one must have height $$\frac{\frac{p(p-1)}{2}}{\frac{p-1}{m}}=\frac{pm}{2},$$but this isn't an integer since $m$ is odd: contradiction. $\blacksquare$ Thus, we may pick some integers $a$ and $b$ where the height of $a$ is greater than the height of $b$, but $a<b$ (since the height of an integer only depends on its modulo-$p$ residue). Consider the $p$-sequences $(c_0,c_1,\ldots)$ and $(d_0,d_1,\ldots)$ with $a=c_0<d_0=b$. Pick the smallest $N$ such that for all $i>N$, we have $c_i>d_i$, which exists due to the height difference that we imposed. Then, the $p$ sequences $(a_0,a_1,\ldots)$ and $(b_0,b_1,\ldots)$ with $a_0=c_N$ and $b_0=d_N$ work, of which there are infinitely many. $\blacksquare$

Someone somehow managed to make me try this problem. Apparently, (a) turns out to be a weak statement. We will prove the following: (a). For any primes $p \notin \{2, 3, 7\}$, there exists $p$-sequences $(a_0, a_1, a_2, \ldots)$ and $(b_0, b_1, b_2, \ldots)$ such that $a_n > b_n$ for infinitely many $n$ and $b_n > a_n$ for infinitely many $n$. This obviously solves part (a). (b). For any odd prime $p$, there exists $p$-sequences $(a_0, a_1, a_2, \ldots)$ and $(b_0, b_1, b_2, \ldots)$ such that $a_0 < b_0$ and $a_n > b_n$ for all $n \geq 1$, if and only if the order of $2$ modulo $p$ is odd. This criterion is satisfied by any primes congruent to $7 \pmod{8}$, thus solving part (b) together with Dirichlet's theorem on arithmetic progressions. I'm going to borrow some ideas from the official solution. For any $n \geq 0$ and odd prime $p$, denote \[ f_p(n) = n + d_p(n), \quad S_p(n) = \sum_{k = 0}^{p - 2} d_p(2^k n). \]In particular, a $p$-sequence is just a sequence of form $(a, f_p(a), f_p^2(a), \ldots)$ for some positive integer $a$ coprime to $p$. For any $n \geq 0$, it is clear that $d_p(f_p(n)) = d_p(2n)$ for any $n \neq 0$. This also implies that \[ f_p^{p - 1}(n) = a + d_p(n) + d_p(2n) + \ldots + d_p(2^{p - 2} n) = n + S_p(n). \]Fermat's little theorem implies $d_p(2^{p - 1} n) = d_p(n)$, so $S_p(2n) = S_p(n)$. As $S_p(n)$ only depends on $n$ modulo $p$, it also means $S_p(f_p(n)) = S_p(n)$. By induction on $k$, we get \[ \forall k \geq 0, \quad f_p^{k(p - 1)}(n) = n + k S_p(n). \]Now, we are ready for both part (a) and part (b).

First, some notation. For any prime $p$, let $f_p(n) = \left \lfloor \frac{n}{p} \right \rfloor$ and $m_p$ be the minimal positive integer where $2^{m_p} \equiv 1 \pmod p$. We will also define $\mathcal{R}_p(n)$ as the number of positive integers $N \leq m_p$ where \[ f_p(a_{N-1})<f_p(a_N) \]given $a_1=n$. Notice that $f_p(a_{N-1})<f_p(a_N) \Leftrightarrow a_{N-1} \pmod p < a_N \pmod p$. Moreover, notice that $f_p(a_{N-1})+1 \geq f_p(a_N)$. For now on, we will assume $2$ is not a generator mod $p$, to say, $m_p<p-1$. Part A Since $\mathcal{R}_p(n) \leq m_p$, by PHP there are positive integers $k < \ell \leq p-1$ where $\mathcal{R}_p(k) = \mathcal{R}_p(\ell)$. Let $a_1=k$ and $b_1=\ell$. By assumption, we have \[ f_ p(a_{tm_p}) = f_p(b_{tm_p}) \text{ for all } t \in \mathbb{N}\]Notice that $f_p(a_t) \not = f_p(b_t)$ for some $t \leq m_p$ since the contrary would imply that $k = \ell$. So, there are $u$ and $v$ not exceeding $m_p$ where $f(a_u) < f(b_u)$ and $f(a_v) > f(b_v)$ which implies that $a_u<b_u$ and $a_v>b_v$. By periodicity, this will occur infinitely often. Part B Notice that if $\mathcal{R}_p(a_0)>\mathcal{R}_p(b_0)$ then for sufficiently large $K$ we have $a_K > b_K$ since the $a_i$ sequence is rolling over more than the $b_i$ sequence. Thus, just choose $k$ and $\ell$ where $\mathcal{R}_p(k) < \mathcal{R}_p(\ell)$. If $k>\ell$ then the sequences where $a_0=k$ and $b_0=\ell$ will have the property that $a_m < b_m$ occurs finitely often, but at least once at $m=0$. So, just keep shifting both sequences over by $1$ until we reach the maximal $M$ where $a_M < b_M$. All values $T>M$ must have the property that $a_T > b_T$. So, starting both sequences at the $M$'th terms gives us what we want. If $k < \ell$, use the fact that $\mathcal{R}_p(k) = \mathcal{R}_p(k+p)$. So, just keep adding $p$'s to $k$ until it gets bigger than $\ell$. Now we have the $k > \ell$ case which we already solved.

sort of weird, but not necessarily in a bad way

Note that $a_{n+1}\equiv a_n+d_p(n)\equiv 2a_n\pmod p$, so $a_n\equiv 2^na_0\pmod p$. Additionally, $a_{n+1}=a_0+d_p(a_0)+d_p(2a_0)+\dots + d_p(2^na_0)$. Yes. Let $p$ be a prime such that $2$ is a quadratic non-residue $\pmod p$, then \[d_p\left(2^{\left(\frac{p-1}{2}\right)}a_0\right)=p-1\]Thus, since terms only depend on the previous term, we have \[\sum_{i=0}^{\frac{p-3}{2}}{d_p(2^ia_0)}=\sum_{i=\frac{p-1}{2}}^{p-2}{d_p(-2^ia_0)}\]\[\sum_{i=\frac{p-1}{2}}^{p-2}{d_p(2^ia_0)}=\sum_{i=0}^{\frac{p-3}{2}}{d_p(-2^ia_0)}\]and so \[\sum_{i=0}^{p-2}{d_p(2^ia_0)}=\sum_{i=0}^{p-2}{d_p(-2^ia_0)}\]Let $a_0=p-1$ and $b_0=p+1$ then we have that $a_{k(p-1)+c}-b_{k(p-1)+c}=a_c-b_c$. Since $a_0<b_0$ and $a_1>b_1$, we are done. Also yes. Let $p>2$ be a prime such that $\text{ord}_2(p)$ is odd. Let $g=\text{ord}_2(p)$. Suppose $a_0$, $b_0$ satisfies $a_0<b_0$ and \[\sum_{i=0}^{g-1}{d_p(2^ia_0)}>\sum_{i=0}^{g-1}{d_p(2^ib_0)}\]then for some large enough $N$, $b_k > a_k$ for all $k>N$. Let $N$ be the smallest such integer that works, and $a_0\to a_{N-1}$ and $b_0\to b_{N-1}$ satisfies the condition. Set $a_0\equiv -b_0\pmod p$ then $d_p(2^ia_0)=p-d_p(2^ib_0)$, which implies that \[\sum_{i=0}^{g-1}{d_p(2^ia_0)}+\sum_{i=0}^{g-1}{d_p(2^ib_0)}=pg\]which is odd. WLOG let \[\sum_{i=0}^{g-1}{d_p(2^ia_0)}>\sum_{i=0}^{g-1}{d_p(2^ib_0)}\]and we can add as many multiples of $p$ as we want to $b_0$. We are done.

(a) Yes. When $p>5$, $a_0=2$ and $b_0=4$ works. This is because $a_i-b_i$ is periodic(because the residues mod $p$ are periodic), $a_0<b_0$, but the turn before $a_i-b_i$ repeats, $a_i$ is missing $1$ and $b_i$ is missing $2$, so $a_i>b_i$. Example with $p=7$: $2,4,1$ and $4,1,2$. Indeed, $2<4$ but $2+4>4+1$. (b) Yes. Restrict $p\equiv 7\pmod 8$ (there are still infinitely many $p$ left by Dirichlet). Note that $2$ is a quadratic residue, and hence not a primitive root. Therefore, the residues mod $p$ can take two different tracks(since $p\equiv 3\pmod 4$). But note that the sum of the residues mod $p$, $\frac{p(p-1)}{2}$, is odd. Therefore, the sum of the two tracks is different. Call these tracks $A$ and $B$, and suppose that the sum of $A$ is less than the sum of $B$. Let $a_0$ be $p$ plus some element of $A$, and let $b_0$ be some element of $B$. Then $a_0>b_0$, but eventually $a_i-b_i$ will always be negative, so just shift $a$ and $b$ until eventually the first index is the only one for which $a_i>b_i$. Example with $p=7$: $A=\{1,2,4\}$, $B=\{3,6,5\}$. Then let $a_0=7+1=8$ and $b_0=3$. Then the sequences go $8,9,11,15,16,18,22,\dots$ and $3,6,12,17,20,26,31,\dots$ so our desired sequence is $9,11,15,16,\dots$ and $6,12,17,20,\dots\;\blacksquare$

For part (a), we'll choose a prime $p$ such that $p \mid 2^q + 1$ for some odd prime $q$. (Such $p$ exists infinitely many, Kobayashi or Zsigmondy whatever) We let $a_0 = p-1$ and $b_0 = p+1$. Then note that $a_1 = 2p-2$ and $b_0 = p+2$, so $a_1 > b_1$ while $a_0 < b_0$. Now let $T = \mathrm{ord}_p(2)$. Then it's clear that $a_n \equiv 2^na_0 (p)$, so $a_n = a_0 + d_p(a_0) + d_p(2^1a_0) + \dots + d_p(2^{n-1}a_0)$. Let $S_a = \sum_{k=0}^{T-1} d_p(2^ka_0)$, $S_b = \sum_{k=0}^{T-1} d_p(2^kb_0)$. Since $a_0 \equiv -1 \equiv 2^q (p)$, so $d_p(2^ka_0) = d_p(2^{k+q})$, therefore $S_a = \sum_{k=0}^{T-1} d_p(2^k) = S_b$. Hence, $a_{Tk+1} = kS_a + a_1 > kS_b + b_1 = b_{Tk+1}$ and $a_{Tk} = a_0 + kS_a < b_0 + kS_b = b_{Tk}$. $\blacksquare$ For part $(b)$, we'll choose a prime $p$ such that $p \mid 2^q - 1$ for some odd prime $q$. Note that $\mathrm{ord}_p(2) = q$. Firstly, we'll prove that $pq \neq 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^{q-1}))$. Since $p \nmid 2^k + 1$ for all $k \ge 0$, so $\{d_p(-2^0), d_p(-2^1), \dots, d_p(-2^{q-1})\} \neq \{d_p(2^0), d_p(2^1), \dots, d_p(2^{q-1})\}$. Therefore, $pq \neq 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^{q-1}))$. Now we'll split the problem into 2 cases: Case 1: $pq > 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^{q-1}))$. We'll prove $p(i+1) > 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^i) + 1)$ for all large $i$. Let $i = qk + s$ and let $S = \sum_{j=0}^{q-1} d_p(2^j)$. Then note that $2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^i) + 1) = 2Sk + 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^s) + 1)$, so our inequality is equivalent to $p(qk + s + 1) > 2Sk + 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^s) + 1)$, or equivalently, $k(pq - 2S) + p(s+1) > 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^s) + 1)$, which is true for large $k$. Now we let $a_0 = p-1$ and $b_0 = p+1$. Then note that $a_{i+1} = p-1 + p(i+1) - (d_p(2^0) + d_p(2^1) + \dots + d_p(2^{i}))$ and $b_{i+1} = p+1 + (d_p(2^0) + d_p(2^1) + \dots + d_p(2^{i}))$ for all $i \ge 0$, so $a_{i+1} > b_{i+1}$ is equivalent to $p(i+1) > 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^i) + 1)$, which is true for all large $i$, and since $a_0 < b_0$, so there exists $j$ such that $a_j < b_j$. We can cut a new $p$-sequence from $(a_n)_{n\ge 0}, (b_n)_{n \ge 0}$, so in this case, we're done. Case 2: $pq < 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^{q-1}))$. We can similarly prove that $p(i+1) < 2(d_p(2^0) + d_p(2^1) + \dots + d_p(2^i) + 1)$ for all large $i$. Pick $a_0 = p+1$ and $b_0 = p-1$, so we see that $a_i > b_i$ for all large $i$. Note that $a_1 < b_1$, so there exists $j$ such that $a_j < b_j$. We can cut a new $p$-sequence from $(a_n)_{n\ge 0}, (b_n)_{n \ge 0}$ similarly, so in this case, we're done exactly same as Case 1. Hence we're done. $\blacksquare$