Solved with mxlcv! The answer is $\boxed{ \text{all odd values of } a_1}$ Note the sequence $a_n$ alternates between odd and even values. Relabel $p(k)$ to $r(k)$. Claim : $a_1$ must be odd. Proof : Let $\mathcal{S}=\{q_1,q_2,\dots,q_t\}$ be the values the sequence $r(a_n)$ takes. Let $p$ be any prime larger than all $q_i$. Let $q=r(a_{p+1})$. Note $q\mid a_{p+1}=a_p^p-1 \implies \text{ord}_q(a_p) = 1 \text{ or } p$. If $\text{ord}_q(a_p)=p \implies p \mid q-1$, which fails for size reasons. Hence $\text{ord}_q(a_p)=1 \implies q \mid a_p-1$. Hence $$a_{p-1}^{p-1} \equiv 2 \pmod {q} \text{ for some } q \in \mathcal{S}$$Now by Dirichlet, consider prime $p$ such that $$p \equiv 1 \left( \text{ mod } \prod_{i=1}^{t}(q_i-1)\right)$$By the above construction, $q_i-1 \mid p-1$, which forces $a_{p-1}^{p-1} \equiv 0 \text{ or } 1 \pmod {q_i}$ for all $q_i \in \mathcal{S}$. But since for some $q \in \mathcal{S}$, we have $ 2 \equiv a_{p-1}^{p-1}$, this forces $q=2$. This implies $$2 \mid a_{p-1} \implies 2 \nmid a_1 \blacksquare$$ Indeed, all odd values work for $a_1$, because: $2 \mid a_{2k}$ for all positive integers $k$, so $r(a_{2k})=2$. $a_4 = \left((a_1-1)^2-1\right)^3-1 \equiv (a_1-1)^2 - 1-1 \not\equiv 0 \pmod{3}$. Hence $a_5 = a_4^4 -1 \equiv 0 \pmod 3$. And if $3 \mid a_n$ where $n$ is odd, then $a_{n+2} = \left(a_n^n-1\right)^{n+1}-1 \equiv (-1)^{n+1}-1 \equiv 0 \pmod 3$. Hence $r(a_{2k+1})=3$ for all $k\geqslant 2$. Hence, we are done!

Congrats to the problem creator, very nice problem!

The answer is $a_1$ odd. Note that $a_{2n-1} \equiv 0 \pmod{p} \implies a_{2n} \equiv -1 \pmod{p} \implies a_{2n+1} \pmod{p}$, so primes dividing some $a_{\text{odd}}$ will divide all of them henceforth and not divide any $a_{\text{even}}$. Furthermore, in general the sequence alternates between odd and even values. If $a_1$ is odd, then we always have $2 \mid a_{\text{even}}$, but by the previous observation $a_1 \mid a_{\text{odd}}$, so $p(a_n)$ is bounded by $p(a_1)$. Now suppose $a_1$ is even, $p(a_n)$ is bounded, and let $p_1,\ldots,p_k$ be the primes (all odd) dividing $a_{\text{even}}$ infinitely often. Claim: For any $i$, we have $p_i \mid a_{j(p_i-1)}$ for all $j$. Proof: Otherwise, $p_i \mid a_{j(p_i-1)+1}$, which is odd, so then it divides all $a_{\text{odd}}$ henceforth and no $a_{\text{even}}$: contradiction. $\blacksquare$ Let $M=(p_1-1)\ldots(p_k-1)$ and $P=p_1\ldots p_k$. Then we have $a_M \equiv 0 \pmod{P} \implies a_{M+1} \equiv -1 \pmod{P} \implies a_{M+2} \equiv -2 \pmod{P}$, since $M+1$ is odd. But this means that none of $p_1,\ldots,p_k$ divide $a_{M+2}$: contradiction, since $M+2$ is even. $\blacksquare$

My problem