What is the smallest prime of the form $n^n+8$?

• Is there a prime of the form $n^n+8$ , $n\in \mathbb N$ ?
• If yes, what is the smallest one ?

It is clear, that $n$ must be odd and cannot be a multiple of $3$ (otherwise $n^n+8$ is of the form $x^3+8=(x+2)(x^2-2x+4)$ and both $x+2$ and $x^2-2x+4=(x-1)^2+3$ are greater than $1$, so $n^n+8$ is not prime).

Furthermore, I verified that $n^n+8$ is composite for all natural numbers below $4000$.

First I checked that there were no primes up to $10^4$ using PFGW. As expected, there were no primes.

Then I considered a rough heuristic: $n^n+8$ is prime with probability $1/\log(n^n).$ Since $$ \int\frac{dx}{x\log x} $$ diverges, you expect infinitely many primes unless something odd happens where all residue classes are ruled out. But this seems unlikely: $21^{21}+8$ has no prime factors below 1801088543, and so you'd need ridiculously long periods to cover the residue classes containing 21.

Looking at the residue classes of the primes up to 17 (this requires working mod 4084080) I find that 5248/36465 of the congruence classes are available for primes, each of which (by virtue of generating numbers relatively prime to 2, 3, ..., 17) is ~5.5394 times more likely to be prime than a typical number of its size. A little bit of summation together with Poisson magic gives a ~16% chance of finding a prime of this form with $n$ from $10^4$ to $10^5$. If that sounds worthwhile, I suggest continuing the calculation to this region -- it would require a few days on a decent machine, nothing crazy.

For comparison, the expected number of primes with $n$ up to $10^{100}$ is about 2.6, so if you get a universe-sized computer and run it for the age of the universe you should be able to find a prime with decent (~92%) probability.