XXIII OBM

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}\ne 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$.