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)$.
In general, is there any prime of the form $\frac{ab^n+c}{\gcd(a+c,b-1)}$ with integer $n\ge1$, for fixed integers $a\ge1$, $b\ge2$, $c\ne0$, $\gcd(a,c)=1$, $\gcd(b,c)=1$? It is unknown whether this problem is solvable, e.g. let $a=4$, $b=72$, $c=-1$, the smallest prime of the form $\frac{4\cdot72^n-1}{\gcd(4+1,72-1)}$ with $n\ge1$ is at $n=1119849$
If we want to solve this problem, we must for every such $(a,b,c)$ integer triple, either find a prime of this form or prove that there is no prime of this form, e.g.:
$(a,b,c) = (78557,2,1)$, in which all numbers are divisible by at least one of $3, 5, 7, 13, 19, 37, 73$
$(a,b,c) = (11047,3,1)$, in which all numbers are divisible by at least one of $2, 5, 7, 13, 73$
$(a,b,c) = (47,8,1)$, in which all numbers are divisible by at least one of $3, 5, 13$
$(a,b,c) = (334,10,-1)$, in which all numbers are divisible by at least one of $3, 7, 13, 37$
$(a,b,c) = (9,4,-1)$, in which all numbers factored as difference of squares
$(a,b,c) = (1,8,1)$, in which all numbers factored as sum of cubes
$(a,b,c) = (25,12,-1)$, in which even $n$ factored as difference of squares and odd $n$ is divisible by $13$
$(a,b,c) = (64,936,-1)$, in which even $n$ factored as difference of squares and $n$ divisible by $3$ factored as difference of cubes and other $n$ divisible by either $37$ or $109$, etc.