How long can the prime chain $a_1=p$ , $a_{n+1}=a_n^2+4$ be at most? We start with a prime number $a_1=p$ and iterate $a_{n+1}=a_n^2+4$ until the next number is composite , for example starting with $3$ gives $3$ , $13$ , $173$ . Here the sequence terminates because the next number, is $29933=37\cdot 809$.

Can such a prime chain be arbitary long ? If no, how many terms can it contain at most ?

The number $\color \red {306167}$ gives a sequence with $5$ entries. If we start with a prime below $10^8$, this is the maximum possible length.
 A: No such chain can be longer than five steps; divisibility by $13$ is an obstruction.  Look at the iterates of the sequence $\bmod 13$ (and note that since $a_n$ only shows up as $a_n^2$ in the mapping, the result for negative residues is the same as for positive ones, so we only have to check residues $1\ldots 6$):


*

*$1\mapsto 1^2+4\equiv5\mapsto 5^2+4\equiv 3\mapsto 3^2+4\equiv13\equiv 0$ . This means that starting from any number $\equiv 1, 3,$ or $5\bmod 13$, a multiple of $13$ will be obtained in at most $3$ steps.

*$2\mapsto 2^2+4\equiv -5$ and immediately falls into the same path.

*$4\mapsto 4^2+4\equiv -6\mapsto 6^2+4 = 1$.


This means that after at most six steps (starting from a number $\equiv 4\bmod 13$), the iteration has to reach a multiple of $13$.
As for where $13$ comes from: while I found it by trial and error, there are a few quick filters that let the search be narrowed.  First, $-4$ (and therefore $-1$) has to be a residue $\bmod p$ for $a^2+4=0$ to have a solution, so only those $p\equiv 1\bmod 4$ need to be checked. Second, $-15$ has to not be a quadratic residue $\bmod p$; otherwise the map has a fixed point $a$ s.t. $a\equiv a^2+4\bmod p$. $13$ happens to be the first prime that meets both of these constraints.  The next is $29$, and it's not too hard to show that $0$ is in the orbit of every residue class $\bmod 29$ as well, but that takes a little more computation. I'm not sure whether the two conditions are enough to ensure that $0$ is in the orbit of every residue class, or whether there are primes $p$ meeting the conditions but with multiple distinct orbits of residue classes.
