2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yes only ONE digit can be removed $\endgroup$ Feb 25, 2021 at 2:28
  • 1
    $\begingroup$ I don’t think there is much that you can do other than brute force it. Your digits can consist of $\{0,3,6,9\}$ and either $n$ digits from $\{1,4,7\}$ or $n$ digits from $\{2,5,8\} $ where $n\equiv 2\pmod 3.$ This condition merely ensures that the number is not divisible by $3$ and 5at removing each digit it is not divisible by $3.$ $\endgroup$ Feb 25, 2021 at 2:43
  • 3
    $\begingroup$ $9977770001777$ is the largest term in the b-file for the sequence, and the largest $< 10^{13}$, but I doubt that it's the largest known. I strongly suspect that if Noe and Resta had given their program an upper bound somewhat larger than $10^{13}$, their program would have found larger examples. $\endgroup$ Feb 25, 2021 at 2:56

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Very nice Misha! We have our first improvement. Can we do better? I expect that we can get numbers with hundreds of digits. $\endgroup$ Feb 25, 2021 at 6:14
  • 1
    $\begingroup$ I certainly wouldn't be surprised if they exist, but finding one is another story. $\endgroup$ Feb 25, 2021 at 6:19
  • $\begingroup$ by the way, why 4 blocks instead of 3? $\endgroup$ Feb 25, 2021 at 7:20
  • 1
    $\begingroup$ Good news: actually there's a 274-digit solution. Bad news; I was beaten to finding it. $\endgroup$ Feb 25, 2021 at 23:57
  • 1
    $\begingroup$ I have a few suggestions for a number that might be larger it is known that $\displaystyle\frac{10^{317}-1}{9}$ and $\displaystyle\frac{10^{1031}-1}{9}$ are primes. These are $317$ ones in a row and $1031$ ones in row respectively. These are called repunit primes. if you tack on a $3$ or a $9$ at one of the ends only two other numbers have to be prime. If you put a $3$ or $9$ in the middle somewhere then three more numbers have to be prime.(tacking on a $7$ will make both numbers divisible by $3$.) I think its highly unlikely but worth testing. $\endgroup$
    – quantus14
    Feb 26, 2021 at 0:31
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Clarified further. $\endgroup$
    – user889417
    Feb 26, 2021 at 3:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .