A digitally delicate prime is a prime number such that if any of its digits are changed by any amount, the result is not prime. The smallest such number is 294001. This means that variations on this number such as 394001 or 291001 or 294081 are all composite.
A paper [1] posted last week gives several new results concerning digitally delicate primes. Here I’ll just mention a few things that are known.
First, there are infinitely many digitally delicate primes. They are uncommon, but they have positive density. That is, as x goes to infinity, the ratio of the number of digitally delicate primes less than x to the total number of primes less than x converges to a small positive number.
This result has been extended to bases other than base 10. In [1] the authors extend the result to widely digitally delicate primes, meaning that the result holds even if you consider the “digits” of a number to include leading zeros.
The following Python code tests whether a number is a digitally delicate prime. It then takes the first six digitally delicate primes and verifies that they are indeed digitally delicate.
from sympy import isprime
from math import floor, log10
def num_digits(n):
return floor(log10(n))+1
def digit_in_pos(n, pos):
return (n // 10**pos) % 10
def set_digit(n, pos, new):
"change digit in given position to new value"
old = digit_in_pos(n, pos)
return n + (new - old)*10**pos
def is_digitally_delicate_prime(n):
if not isprime(n):
return False
nd = num_digits(n)
for pos in range(nd):
for newdigit in range(10):
if digit_in_pos(n, pos) == newdigit:
continue
m = set_digit(n, pos, newdigit)
if isprime(m):
print("m = ", m)
return False
return True
for p in [294001, 505447, 584141, 604171, 971767, 1062599]:
print(is_digitally_delicate_prime(p))
[1] Michael Filaseta and Jeremiah Southwick. Primes that become composite after changing an arbitrary digit. Mathematics of Computation. Article electronically published on November 24, 2020. https://doi.org/10.1090/mcom/3593
I enjoyed your article, and appreciate your posting the code as well. One problem, though: the code as-is will return some “false positives” due to your “range(1, 10)” — changing that to “range(10)” should fix it to properly loop through all ten digits. E.g., the code as-is will mistakenly return True for is_digitally_delicate_prime(504991), because by omitting newdigit=0 it fails to check 504901 (which is a prime obtained from 504991 by altering only one digit, preventing the latter from being a delicate prime). Also, I notice that the code could be made much faster by not evaluating “old” in set_digit(), where it gets evaluated to the same value nine times; instead, it could be evaluated first thing in the outer “for pos” loop and then passed to set_digit() in the inner “for newdigit” loop. (PS: I couldn’t get beyond the paywall for the co-authored paper, but I have benefitted from locating Southwick’s PhD thesis at https://scholarcommons.sc.edu/etd/5879/ — it covers much the same material and includes relevant SageMath code.)
Thanks Robert!
Was happy to see you’d written about said paper after it crossed my radar yesterday. I haven’t read it yet [yes, dumb questions may follow], but the thought struck me that by including leading zeros in the “digits”, i.e. the widely bit; doesn’t that suggest that for a number fitting this widely delicate prime definition that there can be no other prime that also includes the same digits in the same sequence as in the original number?
Also is the trick to this primality test that you can only change “any” digit in the number, including zeros, one at a time instead of multiple at a time; because if multiple at a time were allowed, wouldn’t that suggest that for all numbers excluding the original one that they cannot be prime? The latter seems illogical to me, thus the question.
Nevermind. I should have read the paper first.
I just noticed another problem with this code: it works as though “delicate prime” means that changing any one digit produces a *nonprime* (which includes 1), whereas by the definition such a change must produce a *composite* (which excludes 1). I did a search of the first million primes and found none for which this difference manifested, and I suspect it would only show up in rare cases — such as a prime of form d000…01 having the property that changing any digit except the d produces a composite, and changing the d to anything other than 0 also produces a composite. Such a beast (if exists) would not be delicate, but the program would say it is, because changing the d to a 0 produces a nonprime but not a composite. (Changing your “if isprime(m)” to “if isprime(m) or m==1” would fix this.)
… Ah, instead of homing in on the code, maybe I should have simply said that your article uses a definition of “digitally delicate prime” that differs slightly from the definition used in the reference (i.e., using “nonprime” where the reference uses “composite”).