Part (a): For the contrary, suppose that there are no terms of the sequence which is divisible by $p$. By induction, we get $a_{2^{k}} = 2^{k}.a_{1}$. Now we have $T = 2^{k}.a_{1} = a_{2^{k}} < a_{2^{k} + 1} < \cdots < a_{2^{k + 1}} = 2^{k + 1}a_{1} = 2T$ Lemma 1. The numbers of positive integers which is divisible by $p$ from $1$ to $N$ is $\left\lfloor \frac{N}{p}\right\rfloor$ Lemma 2. $\left\lfloor \frac{2T}{p}\right\rfloor - 2\left\lfloor \frac{T}{p}\right\rfloor \ge 0$ Turn back into our problem, the numbers of numbers which is divisible by $p$ from $T$ to $2T$ is $\left\lfloor \frac{2T}{p}\right\rfloor - \left\lfloor \frac{T}{p}\right\rfloor \ge \left\lfloor \frac{T}{p}\right\rfloor$ On other hand, there are $2^{k} - 1$ terms of the sequence which is in $(T, 2T)$. From the assumption, $a_{i} \not\equiv 0\pmod{p}$ and the sequence is strictly increasing then there are at least $2^{k} - 1$ numbers which is in $(T, 2T)$ and not divisible by $p$, hence there are at most $(T - 1) - (2^{k} - 1) = T - 2^{k}$ numbers which is divisible by $p$ in $(T, 2T)$. Therefore, we have $\left\lfloor \frac{T}{p}\right\rfloor \ge T - 2^{k} \implies \frac{T}{a_{1}} > \frac{T}{p} \ge \left\lfloor \frac{T}{p}\right\rfloor \ge T - 2^{k} \implies 2^{k} \ge 2^{k}a_{1}p - 2^{k}p \implies p + 1 \ge a_{1}p \implies a_{1} = 1$. Now, there are $2^{k} + 1$ terms $a_{i}$ in $[T, 2T]$ and we just have $2^{k} + 1$ numbers in $[T, 2T]$. This implies that there exists some terms of the sequence which is divisible by $p$. However, we conclude that the result.

Suppose for the sake of contradiction that there does not exist an $a_i$ with $p|a_i$. Now take an arbitrary positive integer $k$. We first show that there cannot exist a $k$ such that $a_{k+1}=a_k+1$. This then implies that $a_{2k+2}=2a_{k+1}=2a_k+2$, $a_{2k}=2a_k$, hence $a_{2k+1}=2a_k+1$. Continuing inductively we eventually have $p$ consecutive terms in the sequence all differing by exactly $1$, hence one must be divisible by $p$. Now we show that there cannot exist a $k$ such that $a_{k+1}=a_k+1$. This implies that $a_{2k+2}=2a_k+4$ and $a_{2k}=2a_k$, hence $a_{2k+1}=2a_k+1,2a_k+2,2a_k+3$. But the first and last choices are impossible since then they create two consecutive terms differing by $1$, which we already showed was impossible. Hence $a_{2k+1}=2a_k+2$. Continuing inductively we eventually have $p$ consecutive terms in the sequence all differing by exactly $2$, hence one must be divisible by $p$. Now we show that there cannot exist a $k$ such that $a_{k+1}=a_k+3$. This implies that $a_{2k+2}=2a_k+6$ and $a_{2k}=2a_k$, hence $a_{2k+1}=2a_k+1,2a_k+3,2a_k+3,2a_k+4,2a_k+5$. But all possibilities except $a_{2k+1}=2a_k+3$ are impossible because we have already shown that two consecutive terms cannot differ by $1$ or $2$. Continuing inductively, we eventually have $p$ consecutive terms differing by $3$, hence one must be divisible by $p$. If this idea continues, up to $p-1$, then there cannot exist a $k$ with $a_{k+1}=a_k+\alpha$ for any $\alpha\in\{1,2,3,...,p-1\}$. But this is a contradiction since $a_2-a_1=a_1<p\implies \alpha=a_2-a_1\in\{1,2,3,...,p-1\}$.

Similar to ThE_dArK_lOrD, $a_n=pn+2^{\lfloor \log_2 n\rfloor}$ satisfies. Additionally for all $k\in \mathbb{Z}^+$, then $a_n=pnk+2^{\lfloor \log_2 n\rfloor}$ also works.

Part a: Consider the set \[S=\left\{x\ \Big|\ x=a_{i+1}-a_i,i\in\mathbb N\right\}.\]Since $S$ is a nonempty subset of the natural numbers, we can find a minimal element of $S$. Let this minimal value be $d$, and suppose $k$ is the minimal natural number such that $a_{k+1}-a_k=d$. It's clear that $d<p$ since $d\leq a_2-a_1=a_1<p$. Also, since $a_1<a_2<a_3<\dots$, we must have $d>0$. Now, for large $n$ such that $2^n > p$, consider \[a_{2^n\cdot k},a_{2^n\cdot k+1},\dots,a_{2^n\cdot (k+1)}.\]Note that \[\sum_{i=2^n\cdot k}^{2^n\cdot(k+1)-1}a_{i+1}-a_i=a_{2^n\cdot(k+1)}-a_{2^n\cdot k}=2^n\cdot d.\]But we also, have \[\sum_{i=2^n\cdot k}^{2^n\cdot(k+1)-1}a_{i+1}-a_i\geq \sum_{i=2^n\cdot k}^{2^n\cdot(k+1)-1}d=2^n\cdot d,\]so we must have equality everywhere; this means that \[a_{2^n\cdot k},a_{2^n\cdot k+1},\dots,a_{2^n\cdot (k+1)}\]is an arithmetic sequence with common difference $d$. Since $2^n>p$ and the common difference $d$ satisfies $0<d<p$ (which is relatively prime to $p$), then some term in this arithmetic sequence must be divisible by $p$, so we are done. Part b: Consider the following construction: \[a_i=i\cdot p+2^{\left\lceil\log_2i\right\rceil}.\]This clearly satisfies the condition $a_{2n}=2a_n$ for all positive integers $n$. Also, note that for all $i$, we have \[a_i\equiv 2^{\left\lceil\log_2i\right\rceil}\not\equiv 0\pmod p.\]For concreteness, we list out the first few terms of the sequence based on the definition \[p+1,2p+2,3p+4,4p+4,5p+8,6p+8,7p+8,8p+8,9p+16,10p+16,\dots\]