Largest prime that remains prime when any one of its digits is deleted

Question

Recently I came across this beautiful question: Deleting any digit yields a prime... is there a name for this?

The question talks about primes that remain prime when any one of their digits is deleted (zeros allowed). The answers there claim that there is only a finite number of such primes. So naturally I started wondering what is the largest such prime?

According to A051362 the largest known prime with this property is 9977770001777. Can we find a larger one?

I searched for primes in the form $aa \ldots aabb \ldots bb$, where $a$ and $b$ are digits in $\{1,3,7,9\}$ and there are up to $n \leq 400$ of each one. But I couldn't find any solutions other than the trivial small ones.

Answer 1

About $8$ years ago, not too long after the linked question was asked, Code Golf StackExchange took up the challenge. The winning answer found a $274$-digit solution: $$\underbrace{444\dots 44}_{163} \underbrace{000 \dots 00}_{80} \underbrace{111\dots 11}_{31}$$ This outdoes my own searches considerably. The largest solution I've personally found is the following $84$-digit number, which is the second-largest solution found there: $$\underbrace{444\dots 44}_{50} \underbrace{111 \dots 11}_9 \underbrace{333\dots 33}_{25}$$ It makes sense to test numbers with only a few blocks of consecutive repeated digits: then there's only a few digit deletions to check, so it's more likely that all digit deletions will remain prime. The search I did included:

• All $2$-block numbers with at most $150$ digits per block. The largest solution I found of this form was $222\,223\,333\,333$, which is almost certainly the largest solution there is of this form.
• All $3$-block numbers with at most $50$ digits per block. You can see that the solution above brushes up against this limit, but the second-biggest solution of this form I found only had $32$ digits total. The heuristic below tells us not to expect anything better than the $274$-digit solution.
• All $4$-block numbers with at most $20$ digits per block; I did this before I found the $3$-block solution, or else I would've known not to bother. This gave me the second-largest solution I've found: an "inflation" of $3161$ with $19$ $3$'s followed by $12$ $1$'s followed by $10$ $6$'s followed by $5$ more $1$'s, for $46$ digits total.

Here's a rough probabilistic analysis of how likely such numbers are to have the property we want. There are $9^k \binom{n-1}{k-1}$ distinct numbers with $n$ digits divided into $k$ blocks of digits (like the above has $16$ digits divided into $4$ blocks). Very loosely, this is $9^k \cdot \frac{n^{k-1}}{(k-1)!}$. The probability that a random $n$-digit number is prime is roughly $\frac1{n \ln 10}$. Initially, I estimated that for an $n$-digit number and all $k$ possible digit-deletions to be prime, you pay a factor of $\frac1{(n \ln 10)^{k+1}}$. So we get a probability of $O\Big((\frac{9}{\ln 10})^k \cdot \frac1{(k-1)!} \cdot n^{-2}\Big)$ that there is any solution with $n$ digits and $k$ blocks. The part depending on $k$ is maximized when $k$ is around $4$.

However, looking at the numbers modulo small primes like $2$, $3$, or $5$, there's some correlation. Some of the correlation helps us (spot-checking primes using the last digit) and some hurts us on net (divisibility by $3$ enforces that either digits $1 \bmod 3$ or digits $2 \bmod 3$ must be missing from the number). It's hard to say what the best value of $k$ is, just that it should not grow with $n$.

I've also limited the number of blocks for practical considerations. Even if it turns out that $k=5$ is abstractly more promising than $k=4$, numbers with $5$ blocks will be at least an order of magnitude less likely to result in all the primes we want - there will just be more of them to compensate. So it will take longer to find such solutions.

Answer 2

Primes very much behave like random numbers once you erase the basic properties and you start looking at very large numbers. So your question is if probability of a large number having a property P is $\frac{1}{\ln(n)}$ and we erase one digit, what is the probability of a new number having the same property P.

The question here is quite obvious, and that is which digit you have chosen to delete. Probability that a number $m-k10^n$ has a property P again, directly correlates with $10^n$. So you are asking if $m$ is prime what is the probability of $m-k10^n$ being prime.

Again the average gap between primes is $\ln(n)$ meaning that if you take digits up to $k\log_{10}(\ln(n))$ meaning first few (with some constant k that we can find heuristically), even for a very large number, the rest will keep the probability of $\frac{1}{\ln(\frac{n}{10})}$ for being a prime, regardless which digit you have deleted.

For the first few digits the situation is very complicated and very likely not to be solved any time soon regarding the precise distribution of prime gaps on such a small scale.

So being a prime number, $p$, and deleting a little bit larger digit does not differ much from guessing any prime number that has one digit less. Therefore you can still expect that a new number will be prime with the probability of

$$\frac{1}{\ln(\frac{p}{10})}$$

which is quite large.

Now if you want it for each digit you come up with the probability of the order of

$$\left ( \frac{1}{\ln(\frac{p}{10})} \right)^{\log_{10}(p)-k\log_{10}(\ln(p))} $$

which is the expression of the form

$$\frac{1}{(d-1)^d}$$

where $d$ is the number of digits, explaining why it will be notoriously difficult to verify the existence of the prime with such property with a very large number of digits just by listing them.

The option here is, then, to search for numbers in a specific form so we eliminate quite some number of possible factors when we delete a digit.