Least prime of the form $38^n+31$ I search the least n such that 
$$38^n+31$$ 
is prime. 
I checked the $n$ upto $3000$ and found none, so the least prime of that form must have more than $4000$ digits. I am content with a probable prime, it need not be a proven prime.

This is not a proof, but does not conveniently fit into a comment.
I'll take into account that $n=4k$ is required, otherwise $38^n+31$ will be divisible by $3$ or $5$ as pointed in the comments.
Now, if we treat the primes as "pseudorandom" in the sense that any large number $n$ has a likelihood $1/\ln(n)$ of being prime (which is the prime number density for large $n$), the expected number of primes for $n=4,8,\ldots,4N$ will increase with $N$ as
$$
\sum_{k=1}^N\frac{1}{\ln(38^{4k}+31)}
\approx\frac{\ln N+\gamma}{4\ln 38}
\text{ where }\gamma=0.57721566\ldots
$$
and for the expected number of primes to exceed 1, you'll need $N$ in the order of 1,200,000.
Of course, you could get lucky and find it at much lower $n$, but a priori I don't see any particular reason why it should be...or shouldn't.
Basically, in general for numbers $a^n+b$, the first prime will usually come fairly early, otherwise often very late (or not at all if $a$ and $b$ have a common factor).
Of course, this argument depends on assuming "pseudorandom" behaviour of the primes, and so cannot be turned into a formal proof. However, it might perhaps be possible to say something about the distribution of $n$ values giving the first prime over different pairs $(a,b)$.
