Let $p(k)$ denote the greatest odd divisor of $k$. For a fixed integer $n \ge 2$, let $A_1 = \{j \mid 2^n \le j < 2^{n+1}, p(j) \equiv 1$ $[4]\}$ and $A_2 = \{i \mid 2^n \le i < 2^{n+1}, p(i) \equiv 3$ $[4]\}$. Representing the integers in $[2^n, 2^{n+1})$ in binary $1000...000 \rightarrow 11111...111$, we find easily that $\left\vert{A_1}\right\vert = \left\vert{A_2}\right\vert = 2^{n-1}$. Therefore $a_{2^{n+1} - 1} = a_{2^n - 1} = 1$ for all $n \ge 1$. Now partition the sequence $\{a_k\}_{k \ge 1}$ into sets $\ell_1 = \{1\}$, $\ell_2 = \{2, 1\}$, $\ell_3 = \{2, 3, 2, 1\}$, ..., $\ell_i = \{a_j \mid 2^{i-1} \le j < 2^{i}\}$. We prove that $\max\{\ell_{i+1}\} = \max\{\ell_{i}\} + 1$. If the claim is true, the sequence is unbounded and hits $1$ infinitely many times, so every positive integer occurs in the sequence infinitely many times. To prove the claim, again make use of binary representations. For every integer $a \in$ $[2^i, 2^{i+1})$, after removing trailing zeros from its binary representation, if the resulting binary string ends in '$01$', $p(a) \equiv 1$ $[4]$, if it ends in '$11$', $p(a) \equiv 3$ $[4]$. Because $a_{2^{n+1} - 1} = a_{2^n - 1} = 1$, $a_{2^{n+1}} = a_{2^n} = 2$. Imagine running through the binary strings $10000000..00 \rightarrow 111111...11111$ (from $2^i \rightarrow 2^{i+1}$, *not including $2^{i+1}$). Partition the interval $[2^i, 2^{i+1}) = I_1 \cup I_2 \cup I_3$, where $I_1 = [2^i, 2^i + 2^{i-2})$, $I_2 = [2^i + 2^{i-2}, 2^i + 2^{i-1})$, $I_3 = [2^i + 2^{i-1}, 2^{i+1})$. Map every integer (binary string) $b_1 \in I_1$ to another integer (binary string) $b_1' \in [2^{i-1}, 2^{i-1}+ 2^{i-2})$, by replacing '$10$' at the leftmost end of the string by '$1$', so that $p(b_1) \equiv p(b_1')$. It follows that $a_{b_1} = a_{b_1'}$. Now $a_{2^i + 2^{i-2}} = a_{2^{i-1} + 2^{i-2}} + 2$ because $p(2^i + 2^{i-2}) \equiv 1$ but $p(2^{i-1} + 2^{i-2}) \equiv 3$. Again, mapping the binary string $b_2 \in (2^i + 2^{i-2}, 2^i + 2^{i-1})$ to $b_2' \in (2^{i-1} + 2^{i-2}, 2^i)$ by applying the same procedure as before (replacing leftmost '$10$' by '$1$') we get $p(b_2) \equiv p(b_2')$ and therefore $a_{b_2} + 2 = a_{b_2'}$. Also, we have $a_{2^i + 2^{i-1}} = 2 = a_{2^{i-1}}$. Finally, map every integer $b_3 \in [2^i + 2^{i-1}, 2^{i+1})$ to $b_3' \in [2^{i-1}, 2^i)$ by removing the leftmost '$1$' from the binary string of $b_3$. We have again $a_{b_3} = a_{b_3'}$. The above observations can be described as follows: $\ell_i$ is obtained from $\ell_{i-1}$ by taking the first $2^{i-2}$ terms of $\ell_{i-1}$, then taking the last $2^{i-2}$ terms of $\ell_{i-1}$ but adding $2$ to each term, and finally taking each term of $\ell_{i-1}$ from beginning to end. Therefore $\max\{\ell_{i}\} = \max\{\max\{\ell_{i-1}\}, \max\{\ell_{i-2}\} + 2\}\} = \max\{\ell_{i-2}\} + 2$ by induction. This implies $\max\{\ell_{i+1}\} = \max\{\ell_{i}\} + 1$.

An alternative way to solve part (b) is to consider the average of $a_1, a_2, \cdots, a_{2^k}.$ Notice that for each $k \ge 0$, $a_i$ increases when $i \equiv 2^k \pmod{2^{k+2}}$ and decreases when $i \equiv -2^k \pmod{2^{k+2}}.$ In view of this, define the sequence $s_{k, i}, \forall i \in \mathbb{N}$ by $s_{k, i} = 1$ if $i \equiv 2^k, 2^{k+1}, \cdots,$ or $2^{k+1} + 2^k - 1$ (mod $2^{k+2}$) and $s_{k, i} = 0$ else. Then observe that each $a_i = \sum_{k = 0}^{\infty} s(k, i).$ Now, we may compute the average of the terms $a_1, a_2, \cdots, a_{2^k}.$ Indeed, this is computed by summing the averages of the terms $s_{j, 1}, s_{j, 2}, \cdots, s_{j, 2^k}$ for all $j \in \mathbb{Z}_{\ge 0}.$ This is clearly positive for all $j \in \mathbb{N}$, and for $j \le k-2$ this is precisely $\frac12.$ Hence, we have that the average of $a_1, a_2, \cdots, a_{2^k}$ is at least $\frac{k-1}{2}$ for all $k \in \mathbb{N}$. From this, it's clear that $\{a_n\}$ grows to arbitrarily large values, and so since it changes by at most $1$ each time and starts at $1$, it must hit all positive integer values. $\square$

First of all, note that it's enough to show that there are infinitely many ones in the sequence and that every natural number appears (since we can apply IVT on the positive integers, that is, because $|a_{n}-a_{n-1}|=1$, this implies that between a $1$ and an integer $N$, all integers $1\leq x\leq N$ must have appeared). After writing out the first members of the sequence, one may notice that $a_{2^{k}-1}=1$ for all $k$ (can be shown by induction, but we won't do that). However, we can actually characterize the sequence completely. Write $n$ in binary and label the digits from right to left as $d_{0},d_{1},d_{2},\dots $ with infinite leading zeros. Call an index $i$ quirky if $d_{i}-d_{i+1}\neq 0$. Then the crucial claim is that $a_{n}$ is equal to the number of quirky indices. Indeed, this is the case for $n=1,2,3$ which we'll use as a base case and prove this claim by induction on $n$. Assume that the statement holds for all integers $n\in \{1,2,\dots ,m\}$. We'll also prove it for $n=m+1$. There are the following cases for the ending digits of $m$: Case 1. $d_{0}=0$. Then if $4\mid m$, we have that $m=\overline{\dots 00}_{(2)}$ and $m+1=\overline{\dots 01}_{(2)}$. Clearly, $a_{m+1}=a_{m}+1$ as $m+1\equiv 1\pmod 4$ and also the number of quirky indices has increased by $1$ because now $i=0$ is quirky and previously it wasn't, so we've completed the induction step. If $4\nmid m$, then $m=\overline{\dots 10}_{(2)}$ and $m+1=\overline{\dots 11}_{(2)}$. Then both the number of quirky indices decreases by 1 and $a_{m}-a_{m+1}=1$ as $m+1\equiv 3\pmod 4$ and we've removed the previously quirky index $i=0$, hence we're done in this case as well. Case 2. $m=\overline{\dots 00111\dots 1}_{(2)}$. Then $m=\overline{\dots 01000\dots 0}_{(2)}$, so the number of quirky indices increases by $1$ and the largest odd divisor of $m+1$ is of the form $4k+1$ (obvious by the binary representation), so the statement is true for $m+1$ as well. Case 3. $m=\overline{\dots 10111\dots 1}_{(2)}$. Then $m=\overline{\dots 11000\dots 0}_{(2)}$, so the number of quirky indices decreases by $1$ and the largest odd divisor of $m+1$ is of the form $4k+3$ (obvious by the binary representation), so the statement is true for $m+1$ as well. Thus the induction is complete and we've characterized $a_{n}$ with the binary representation of $n$. Now the fact that $a_{2^{k}-1}=1$ is obvious, so there are indeed infinitely many ones in the sequence. Also, note that if $N=1+2^2+2^4+\dots +2^{2t}$, then $a_{N}=2t+1$, so every positive integer appears infinitely many times in the sequence due to what we mentioned in the beginning.