Problems & Puzzles: Puzzles

Puzzle 398. 369293 Perhaps you have seen this curio about the prime 369293 369293 The smallest prime which cannot become another by inserting a digit (neither appending it at the extremes, CR). [Blanchette] It's a kind of easier to get a few more of them: 369293, 5364431, 7904521, 9387527, 9510341, 22038829, 39113161,  43744697, 56618161, 57640663, ...  But I intuit that there must be only a finite quantity cases of this type. Question. 1. Can you argument on favor or on the contrary of my intuition? 2. If my intuition is correct can you find the largest case of this type of primes?

---

Contributions came from Giovanni Resta, J.K.Andersen, Adam Stinchcombe & Farideh Firoozbakht.

All of them demonstrated that my intuition was wrong, using more or less the same argument:

Consider a prime p with n-1 digits. There are approximately 10n ways to
insert a digit in p and get an n-digit number ending in 1, 3, 7 or 9.
A random n-digit number has chance around 1/log(10^n) of being prime. When it is not divisible by 2 or 5, this becomes 2 * 5/4 * 1/log(10^n) =
2.5/(log(10)*n) ~= 1.1/n. If we assume the 10n required composites behave
randomly for numbers coprime to 10, then the heuristic chance of all being
composite is around (1-1.1/n)^(10n). This approaches a number near 1/60000 for large n, so I expect a positive ratio of primes to have this property.

Andersen adds that:

According to http://www.math.sc.edu/~kozek/abstracts.pdf  (apparently
unpublished currently) there are infinitely many composite numbers coprime
to 10 with this property. I can imagine how it could be proved for composites by finding a covering set of prime factors. A proof for primes seems much harder. I can imagine covering sets which show there are infinitely many numbers of forms that are likely to include infinitely many primes. But I guess it would be very hard to prove whether such forms really have infinitely many primes. I have not searched for such forms.

All noticed that my list of small cases was not complete:

http://www.research.att.com/~njas/sequences/A125001  lists the smallest
primes with this property. The list in the puzzle is non-exhaustive. It skips
16 primes.

The largest example gotten by some of them was:

10^999 + 33592689 (Resta)

10^299+3173337 (Andersen)

10^199+7993389 (Farideh)

***

 

 

---