I search the least n such that
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 38n+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,…,4N will increase with N as
N∑k=11ln(384k+31)≈lnN+γ4ln38 where γ=0.57721566…
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 an+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).