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.
Solution 1:
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)$.
Solution 2:
Primality of numbers of the form $a^n+b$ is a very hard problem in general. For instance, existence of primes of the form $4294967296^n+1=(2^{32})^n+1$ is an old open problem in number theory (wiki), although it is also easy to show that this can be a prime only for $n$ of a special form (powers of $2$). Your problem $2085136^n+31=(38^4)^n+31$ does not seem much easier.
In other words, a theory-based answer to your problem is very unlikely in the near future. For a practice-based answer you will probably need to use some distributed computing project for searching for prime numbers like PrimeGrid, which has found most of the known large primes of the form $ab^n+c$.