We show first that if (1) $a_n$ is prime, (2) all terms $a_i$ for $i < n$ are primes or prime powers, (3) given any prime $p < a_n$, we have $p \mid a_i$ for some $i < n$, then $a_i$ is prime for all $i > n$. For suppose $a_n < k < q$, where $q$ is the next larger prime than $a_n$. Then $k$ lies between two consecutive primes, so it must be composite. So it must have a prime factor less than $a_n$. By (3) that must divide $a_i$ for some $i < n$. Hence $a_{n+1} \neq k$. On the other hand $q$ is obviously coprime to all $a_i$ for $i \le n$, so $a_{n+1} = q$.

* $a_0 = 2$ gives all terms primes.
* $a_0 = 3$ gives $a_1 = 4$, $a_2 = 5$ and hence all higher terms prime.
* $a_0 = 4$ gives $a_1 = 5$, $a_2 = 7$, $a_3 = 9$, $a_4 = 11$, and hence all higher terms prime.
* $a_0 = 5$ gives $a_1 = 6$, which is not a prime or prime power.
* $a_0 = 6$ is not a prime or prime power.
* $a_0 = 7$ gives $a_1 = 8$, $a_2 = 9$, $a_3 = 11$, $a_4 = 13$, $a_5 = 17$, $a_6 = 19$, $a_7 = 23$, $a_8 = 25$, $a_9 = 29$, and hence all higher terms prime.
* $a_0 = 8$ gives 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53 and hence all higher terms prime.
* $a_0 = 9$ gives $a_1 = 10$, which is not a prime or prime power.

Now suppose $a_0 > 9$. We show first that there are no solutions to $3^k = 2^h \pm 1$ for $k > 2$. Consider $3^k = 2^h+1$. If $k > 2$, then $h > 3$, so $3^k - 1 = (4-1)^k - 1$ is divisible by 4, so $k$ must be even. Put $k = 2m$. Then $2^h = (3^m+1)(3^m-1)$. But $3^m - 1$ and $3^m + 1$ cannot both be powers of 2 for $m > 1$, so there are no solutions for $k > 2$. Consider $3^k = 2^h - 1$. Again $2 = (3-1)$, so $h$ must be even. Put $h = 2m$, then $3^k = (2^m-1)(2^m+1)$. But $2^m - 1$ and $2^m + 1$ cannot both be powers of 3 for $m > 1$. So there are no solutions for $k > 2$.

Now if $a_0 = 6n$, then $a_0$ is obviously not a prime power. If $a_0 = 6n - 1$, then $a_1 = 6n$, which is not a prime power. If $a_0 = 6n + 1$, then $a_1 = 6n + 2$, which is divisible by 2. So if it is a prime power, then it must be a power of 2. But $a_2 = 6n + 3$, which is divisible by 3, so it can only be a prime power if it is a power of 3. We have just shown that is impossible for $a_0 > 9$. Thus
$a_0 = 6n+1$ fails for $a_0 > 9$. Similarly, if $a_0 = 6n+2$, then $a_0$ must be a power of 2, and $a_1 = 6n+3$ must be a power of 3, which is impossible for $a_0 > 9$. Similarly, if $a_0 = 6n+3$, $a_1 = 6n+4$ and again they cannot both be prime powers.

We claim that there are no solutions to $3^k = 2^h + 5$ for $k > 2$. Putting $3 = 4-1$, we see that $k$ must be even. Putting $2 = 3-1$, we see that $h$ must be even. Put $k = 2K$, $h = 2H$, then $3^{2K}-2^{2H} = 5$, so $(3^K+2^H)(3^K-2^H) = 5$. But that is impossible for $K > 2$ and hence $k > 4$. It is easy to see that $3^4-5$ and $3^3-5$ are not powers of 2. If $a_0 = 6n-2$ then $a_1 = 6n-1$, $a_2 = 6n+1$, $a_3 = 6n+3$. Then $a_0$ must be a power of 2 and $a_3$ must be a power of 3. But we have just shown that is impossible for $a_0 > 9$.