4. Let $m=n-1, a_{i}=b_{i}-1$, then $1 \leqslant a_{0} \leqslant 2 m$, and
$$a_{i+1}=\left\{\begin{array}{ll}
2 a_{i}, & a_{i} \leqslant m, \\
2 a_{i}-(2 m+1), & a_{i}>m .
\end{array}\right.$$

This indicates: $a_{i+1} \equiv 2 a_{i}(\bmod 2 m+1)$, and for $i \in \mathbf{N}$, we have $1 \leqslant a_{i} \leqslant 2 m$.
(1) The required values are equivalent to finding $p\left(1,2^{k}-1\right)$ and $p\left(1,2^{k}\right)$ for $\left\{a_{i}\right\}$. The former is equivalent to finding the smallest $l \in \mathbf{N}^{*}$ such that
$$2^{l} \equiv 1\left(\bmod 2\left(2^{k}-1\right)+1\right) ;$$

The latter is equivalent to finding the smallest $t \in \mathbf{N}^{*}$ such that
$$2^{t} \equiv 1\left(\bmod 2^{k+1}+1\right)$$

Since $2\left(2^{k}-1\right)+1=2^{k+1}-1$, and for $1 \leqslant l \leqslant k$, it is clear that $2^{l} \neq 1\left(\bmod 2^{k+1}-1\right)$, hence $p\left(1,2^{k}-1\right)=k+1$. Also, $2^{2(k+1)} \equiv 1\left(\bmod 2^{k+1}+1\right)$, so $\delta_{2^{k+1}+1}(2) \mid 2(k+1)$. But for $1 \leqslant t \leqslant k+1$, we have $2^{t} \neq 1\left(\bmod 2^{k+1}+1\right)$, thus $p\left(1,2^{k}\right)=\delta_{2^{k+1}+1}(2)=2(k+1)$.

Therefore, for $\left\{b_{i}\right\}$, we have $p\left(2,2^{k}\right)=k+1, p\left(2,2^{k}+1\right)=2(k+1)$.
(2) We still discuss in terms of $\left\{a_{i}\right\}$, and need to prove: $p\left(a_{0}, m\right) \mid p(1, m)$.
First, let $p(1, m)=t$, then $2^{t} \equiv 1(\bmod 2 m+1)$, and thus $2^{t} a_{0} \equiv a_{0}(\bmod 2 m+1)$, so $p\left(a_{0}, m\right) \leqslant p(1, m)$.

Second, if $p\left(a_{0}, m\right) \times p(1, m)$, then we can set
$$p(1, m)=p\left(a_{0}, m\right) q+r, 0<r<p\left(a_{0}, m\right)$$

Let $s=p\left(a_{0}, m\right), t=p(1, m)$, then combining $2^{s} a_{0} \equiv a_{0}(\bmod 2 m+1)$, we know
$$a_{0} \equiv 2^{t} a_{0}=2^{n+r} a_{0} \equiv 2^{s(q-1)+r} a_{0} \equiv \cdots \equiv 2^{r} a_{0}(\bmod 2 m+1),$$

which contradicts the minimality of $s$.
Therefore, $p\left(a_{0}, m\right) \mid p(1, m)$, and the proposition is proved.
4. Let $n, b_{0} \in \mathbf{N}^{*}, n \geqslant 2, 2 \leqslant b_{0} \leqslant 2 n-1$. The sequence $\left\{b_{i}\right\}$ is defined as follows:
$$b_{i+1}=\left\{\begin{array}{ll}
2 b_{i}-1, & b_{i} \leqslant n, \\
2 b_{i}-2 n, & b_{i}>n,
\end{array} \quad i=0,1,2, \cdots\right.$$

Let $p\left(b_{0}, n\right)$ denote the smallest index $p$ such that $b_{p}=b_{0}$.
(1) For $k \in \mathbf{N}^{*}$, find the values of $p\left(2,2^{k}\right)$ and $p\left(2,2^{k}+1\right)$;
(2) Prove that for any $n$ and $b_{0}$, $p\left(b_{0}, n\right) \mid p(2, n)$.