Puzzle 291.  Primes embedding a given sequence

***

Andrew wrote:

I have an answer for your third question, and it gives an idea of where to search for an S for the first two parts, namely with really big numbers. Here's my reasoning (again with a corollary):

We can give an upper bound on L(SP) as follows: suppose L(S) = d, say S = s_1s_2…s_d where s_i is a digit. If gcd(S,10) is greater than 1, then we append a 1 onto the right of S and let the resulting string be our new S. Now we have that k*10^d+S for k>0 is prime infinitely often by Dirichlet's theorem. Next we apply Linnik's theorem to find that there is a prime in this sequence below
10^(2d) [it is known that 2 will work here almost all the time and is conjectured to hold universally]. We shall assume for simplicity that 2 holds universally. Therefore L(SP) <= 2d for every sequence S [note that for large S this is a horrendous upper bound as we shall see below]. This immediately
gives:
Corollary: L(SP) grows linearly with respect to L(S) since 1<= L(SP)/L(S) <= 2 for all S by the above, i.e o(L(S)) = o(L(SP)).
Therefore if we want a sequence for which L(SP) = L(S) + 5, we must begin with L(S) => 5 (any sequence S of 4 or fewer digits necessarily has L(SP) <
L(S)+5 as a consequence of Linnik's theorem). Now consider a given S. If we append 5 random digits onto the front of it, we must have that the 10^4 digit combinations in which the leading digit is 0 are not prime (for if one were, we would have L(SP) < L(S)+5. By the prime number theorem we have that the odds of a random number x being prime is about 1/ln(x), so when ln(x) > 10^4 we will have that it is likely that the first prime occurs after these first 10^4 terms of the arithmetic sequence; this occurs about 10^4343. Note also that we are assuming S is on the right of SP, we have not calculated when it is in the middle or on the left, such a correction will change the estimate below by some orders of magnitude but should not affect the asymptotic behavior predicted. Of course we could very well have that an S with fewer than 4343 digits has L(SP) = L(S) + 5, this is just the area where we expect that a random sequence will give the +5 result. Based on the speed of growth required to find a sequence where it is likely that L(SP) = L(S) + 5, combined with the prior corollary to Linnik's theorem, I would guess that in the long run L(SP) grows at exactly the same rate as L(S); i.e. L(SP)/L(S) tends to 1 as S grows large.
 

***