Arbitrarily Deletable Primes

This was an interesting mathematical exploration.

I recently watched this video about left-truncatable primes. A left-truncatable prime is a prime number that, when any number of left-most digits are removed, results in another prime number [1, 2, 3, 4].

The video also discussed right-truncatable primes, which are primes that when truncated from the right result in other primes and deletable primes, which are primes where a digit can be removed from somewhere in the number and result in a new prime and there is some sequence of those deletions that results in a prime at each step until there are no digits remaining [5, 6].

Towards the end of the video, Brady Haran asks if there is a number, specifically a deletable prime, where it doesn't matter which digit you delete to result in a prime number. The question intrigued me so I decided to spend a bit of time thinking about it.

Well, it turns out that not too long after thinking about this in some detail, you can quickly realize there aren't many. In fact, the complete list of these primes is: 2, 3, 5, 7, 23, 37, 73.

Before I go on to explain my thought process, I would like to acknowledge that there are at least a few other who have already tackled this problem. After undergoing this thought exercise myself I went back and reviewed the comments on the original video. There, I discovered that YouTube user Tantusar already identified the complete list of these primes, naming them "Arbitrarily Deletable Primes".

Defining Arbitrarily Deletable Primes

Based on the question proposed above, we define an arbitrarily deletable prime as a deletable prime for which any digit may be deleted resulting in a new prime and that this be repeatable until there are not digits remaining.

Proof

We begin with digits 0-9.

• 1 is not prime. If it exists in a number, some combination of digit deletions can result in the remaining number being 1. Therefore, the digit 1 cannot appear in a arbitrarily deletable prime.
• 2 is prime and if we count 1-digit numbers as arbitrarily-deletable primes, it is our first arbitrarily-deletable prime. It can be part of a larger arbitrarily-deletable prime, but only if it is the left-most digit. Otherwise a deletion sequence will exist that makes 2 the right-most digit. This is only a prime if 2 is the only remaining digit.
• 3 is prime and can be used in larger arbitrarily-deletable primes.
• 4 is not prime and cannot be used in arbitrarily-deletable primes.
• 5 is prime and can be used in larger arbitrarily-deletable primes as long as it it the lest-most digits for the same reasoning that this must be done for 2.
• 6 is not prime and cannot be used in arbitrarily-deletable primes.
• 7 is prime and can be used in larger arbitrarily-deletable primes.
• 8 is not prime and cannot be used in arbitrarily-deletable primes.
• 9 is not prime and cannot be used in arbitrarily-deletable primes.

So far our arbitrarily-deletable primes are: 2, 3, 5, and 7. And these are the only digits that can be used to make larger primes. With 2 and 5 only being allowed as the left-most digit.

Moving on to creating 2-digit arbitrarily-deletable primes, we can extend our starting point of 2 by adding 3's or 7's to it.

• 23 is prime and is our next arbitrarily-deletable prime.
• 27 is not prime, so we will forget about it.

Starting with a 3, we can create:

• 33 is not prime, but we can observe something useful here that we'll discuss in just a moment.
• 37 is prime and is our next arbitrarily-deletable prime.

Starting with a 7, we can create:

• 73 is prime and is our next arbitrarily deletable prime.
• 77 is not prime and we observe the same thing here as with 33.

What we observe by looking at 33 is that repeating digits always creates a number divisible by 11. Thus including the same digit twice in a number would allow for a series of deletions where those two numbers are the only ones remaining and thus the number would not be prime. This gives us the constraint that no digit can be used twice in a arbitrarily-deletable prime number.

That constraint also implies another interesting one: an upper bound on the size of arbitrarily-deletable primes. If every digit could only be used once our upper bound would look something like 9,876,543,210. However, since many digits cannot be used at all and some (like 2 and 5 must be left-most digits) we have a much smaller upper bound of 573 just from our already defines rules.

We can take that a step further by realizing 573 is not prime, neither is 537, 273, or 237. We rule out 3-digit numbers starting with 3 or 7 because we cannot create 3-digit numbers with only those two non-repeating digits.

So, we cannot create any arbitrarily-deletable 3-digit primes giving us a complete and rather short list of arbitrarily-deletable primes of: 2, 3, 5, 7, 23, 37, 73.

Arbitrarily deletable primes in other bases

What's interesting is the divisible by 11 constraint described above can be used to place an upper bound on arbitrarily deletable primes for any number base. An interesting property of the number 11 for any base is that when any single digit, N, is multiplied by it (regardless of base), the result is the number represented by NN. Try it. Here is some JavaScript code that will do this up to base 36.

// Loop through base 2 to base 36
for (let i = 2; i <= 36; i++) { 
  // For each digit in the base mu;tiply it by 11 in that base
  for (let j = 1; j < i; j++) { 
    let digit = j.toString(i);
    let digitAsNumber = parseInt(digit, i);
    let elevenBasei = parseInt('11',i);
    let result = Number(digitAsNumber * elevenBasei);
    let resultBasei = result.toString(i);
    console.log('Base', i.toString() + ':', digit, '* 11 =', resultBasei); 
  }
}

What this tells us is that any arbitrarily deletable prime cannot contain the same digit twice. Or to phrase that differently, if a number contains the same digit twice (let's call it N), there is a sequence of deletions that result in the number NN which is never prime because NN in any base is always divisible by 11.

Conclusion

It turns out this did not end up being a particularly interesting problem, however is was fun to reason about and think through despite a rather uninteresting result.