66
$\begingroup$

Suppose for the purpose of this question that number $1$ is a prime number.

Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If we removed $3$ instead of $1$ we would arrived at the number $11$ which is prime. If we remove $3$ from the number $31$ we arrive at the prime number $1$ and if we remove $1$ from $31$ we arrive at the number $3$ which is prime. And if we removed number $1$ from the number $11$ we would arrive at the prime number $1$.

So what property does this number $311$ have?

It has the property that if we remove one digit in any way we want we arrive at the prime number and if we remove two digits in any way we want we also arrive at the prime number. (Of course, if the original prime number had $n$ digits then it should be prime whatever $k$ digits we remove, for $1\le k\le n-1$.)

The question would be:

Are there an infinite number of prime numbers so that removing any number of digits leaves us with a prime number?

It seems to me that big enough prime numbers will rarely have the property that for every possible removal of some of the digits we will arrive at the prime number, but I see no reason that forbids an infinite number of these prime numbers.

$\endgroup$
  • 10
    $\begingroup$ Infinitely many seems very doubtful, since almost all the digits have to be $3$. $\endgroup$ – André Nicolas May 1 '16 at 16:07
  • 6
    $\begingroup$ If there is a $5$ there, it has to be the most significant digit. $\endgroup$ – Arthur May 1 '16 at 16:14
  • 1
    $\begingroup$ @Arthur We can also eliminate places where 2 can be. $\endgroup$ – Farewell May 1 '16 at 16:15
  • 64
    $\begingroup$ As a side note, $1$ is not prime $\endgroup$ – Stella Biderman May 1 '16 at 16:24
  • 5
    $\begingroup$ Using @AndréNicolas' solution, we can carry this out by hand. If $2$ or $5$ is not the leading digit, the only possible digits are $1, 3, 7$. Since we cannot repeat $3$ or $7$ (as we could produce $33$ or $77$), the only $3$-digit possibilities that start with $7$ are $731, 713, 711$, but all of these are composite. The leading digit cannot be $5$, as $51, 57$ are composite and $533$ has two $3$'s. Finally, $371$ is composite, bringing us to $317$. $\endgroup$ – Travis May 1 '16 at 16:52
124
$\begingroup$

It is clear that we cannot have digits $0,4,6,8,9$ in those prime numbers. There can be at most one $2$ because $22$ is composite,, at most one $3$ because $33$ is composite,at most one $5$ because $55$ is composite, at most one $7$ because $77$ is composite, at most two $1$`s because $111$ is composite, so such prime number can have at most $6$ digits so there is a finite number of such prime numbers.

$\endgroup$
  • 5
    $\begingroup$ More over, the $2$ should be the first digit from the left. Otherwise after removing the digits to the right of the $2$, we could always arrive at an even number. $\endgroup$ – Aritra Das May 1 '16 at 17:04
  • 6
    $\begingroup$ Farewell: you know that, but the reader that arrived here and read your answer didn't. @AritraDas is improving on your answer. $\endgroup$ – Mindwin May 2 '16 at 20:04
  • 4
    $\begingroup$ @Mindwin, no, the question was whether there are an infinite number, and this answer suffices as is to show there are not. Nothing needs to be added, and no addition (among the ones mentioned) will improve it. $\endgroup$ – msh210 May 3 '16 at 0:43
  • 6
    $\begingroup$ Technically there should be zero "1" because 1 is not prime thus allowing the number to degenerate into 1 would render it a non-prime. $\endgroup$ – slebetman May 3 '16 at 7:22
  • 15
    $\begingroup$ @slebetman: "technically" you should read the question, which states very clearly that 1 is to be considered "prime" for the purposes of the question. Mathematics has the absolute right to define notation, and everywhere in this question and its answers, "prime" means "prime or equal to 1" ;-p $\endgroup$ – Steve Jessop May 3 '16 at 10:02
81
$\begingroup$

To build on the earlier answers, there are exactly twenty such numbers, and they are:

1, 2, 3, 5, 7, 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 311, 317

As can be found by the following program, which is correct as per Farewell's argument that seven digit and longer numbers cannot have the given property:

import gmpy

def test(n):
    if (not gmpy.is_prime(n)) and n != 1:
        return False
    s = str(n)
    if len(s) == 1:
        return True
    for i in xrange(len(s)):
        if not test(int(s[:i] + s[i+1:])):
            return False
    return True

print filter(test, xrange(10000000))

It is further worth noting that this program's output list is clearly exhaustive even barring Farewell's argument; the moment we fail to find any four digit examples we exclude the possibility of five digit (or longer) examples, as they must include four digit examples as substrings.

$\endgroup$
  • 25
    $\begingroup$ Here starts the debate on whether computer-verification counts as proof. (I vote "yea".) $\endgroup$ – Daniel R. Collins May 1 '16 at 22:08
  • 3
    $\begingroup$ @MaxvonHippel: Why do you presuppose that there is a good conceptual explanation? Perhaps, since this had to be a finite set, those twenty numbers "just happened" to be the ones that fit the requirements. $\endgroup$ – Kevin May 2 '16 at 0:07
  • 7
    $\begingroup$ @MaxvonHippel: Number theory (and anything to do with the intrinsic nature of natural numbers as opposed to reals) is the last place where you expect to find conceptual explanations. For example, find all positive integer solutions $(x,y)$ satisfying $x^3 + 3 = y^7$... To clarify, this does not mean that there is never a conceptual explanation, but that one should not expect it by default. $\endgroup$ – user21820 May 2 '16 at 3:25
  • 12
    $\begingroup$ @YoTengoUnLCD: Looks like Python to me. $\endgroup$ – user21820 May 2 '16 at 4:35
  • 11
    $\begingroup$ Your sequence is a subsequence of OEIS A068669 (where they have the weaker requirement that all substrings (i.e. consecutive strings of figures) are non-composite). A068669 has twenty-four members. $\endgroup$ – Jeppe Stig Nielsen May 2 '16 at 8:31
48
$\begingroup$

There are only finitely many, indeed there are none with more than $3$ digits. Clearly our prime cannot have $0$ as a digit.

If our prime has $4$ or more digits, and has $2$ or more not equal to $3$, we can by deleting one or two get a number greater than $3$ with digit sum divisible by $3$.

And if there are two or more $3$'s we can produce $33$.

$\endgroup$
  • 1
    $\begingroup$ @Farewell "Use comments to ask for more information or suggest improvements. Avoid comments like "+1" or "thanks"." Literally. I suggest the improvement that you guys read what the comment box say. :P $\endgroup$ – pipe May 4 '16 at 12:42
31
$\begingroup$

Extending André's answer and Travis's comment:

Firstly, a 0 digit is ruled out since by definition it cannot be the first digit, and in any other position we could delete everything that follows it to leave a multiple of 10. All of which are composite since 10 is.

With 0 excluded, every digit must be prime (1, 2, 3, 5, 7) because we could delete everything else to leave a one-digit number. Note in particular that if a digit is 0 modulo 3 then it is 3.

With four or more digits, two of them are equal modulo 3 by the Pigeonhole Principle. Taking the digits modulo 3, we must have either:

  • Two 0s, that is to say two 3s. But then by deleting all other digits we have 33, which is not prime.

  • Two 1s (mod 3). Consider any two of the other digits. Either they are both 0 mod 3 (which is the above case); or else one of them is a 1 (so we can form a three-digit number whose digits are all 1 mod 3 and therefore with digit sum divisible by 3 and hence which is composite); or else one of them is a 2 (in which case we can form a two-digit number with a 1 and a 2 and hence which is composite).

  • Two 2s (mod 3). Same as above, with 1 and 2 reversed.

So solutions have at most three digits. For three-digit numbers, we can't have a 2 or a 5 after the first digit because $x2$ and $x5$ are divisible by 2 or 5 respectively. So digits after the first are taken from 1, 3, 7. Consider the first digit:

  • 7: Then the other two digits can't be 7 again, leaving us combinations of 1 and 3. They can't both be 1 (that's 3 digits all 1 mod 3), and they can't both be 3 (that's two 3s), leaving $713 = 23 \times 31$ and $731 = 17 \times 43$. No solutions.

  • 5: 51, and 57 are composite, so there are no 1s or 7s, leaving 533 (which is two 3s). No solutions.

  • 3: We can't have another 3, leaving combinations of 1 and 7. 377 has a repeated 7; $371 = 7 \times 53$; but $311$ and $317$ are both solutions. Hence $317$ is the largest solution.

  • 2: 21 and 27 are composite, leaving only 3, which we can't repeat. No solutions.

  • 1: The other two digits are combinations of 1, 3, 7. All three digits can't be 1 mod 3 (see above), so one of the digits must be a 3. But not both. The other digit is a 1 or a 7. This gives $113$, $131$, $137$, $173$ which are all solutions.

Consider 2 digit numbers if you can be bothered. Just pick out the primes consisting of two prime digits.

Finally, the 1-digit primes 1, 2, 3, 5, 7 are all solutions of course.

$\endgroup$
  • $\begingroup$ Ingenious solution. Just want to ask you what inspired to you pick mod 3 from the start? Was it trial and error? $\endgroup$ – Hans May 24 '16 at 19:52
  • $\begingroup$ @Hans: because it's a question about digits and divisibility. When you're looking at base 10 digits it's quick to rule out a lot of non-primes by considering divisibility by 2 (i.e. is the last digit even) and divisibility by 3 (i.e. is the digit sum 0 mod 3). $\endgroup$ – Steve Jessop May 24 '16 at 21:30
11
$\begingroup$

I thought about what happens in bases b other than b = 10.

We cannot have the digit zero, or any digit that is a composite number (for example in hexadecimal: 4, 6, 8, 9, 10, 12, 14, 15). The possible digits are the number 1 and the primes p < b.

No digit other than 1 can appear more than once, since xx = x * 11 in every base. The digit 1 can appear at most three times, since 1111 = 11 * 101 in every base.

If the base b is odd, then a number de is even if d and e are both odd, so a solution x cannot contain two odd digits. The best we can ask for is 2d or d2 where d is an odd prime or 1.

Otherwise the base b is 6k, 6k+2, or 6k+4. If b = 6k+4 then x modulo 3 equals the sum of the digits, modulo 3. A solution x cannot contain both digits d = 1 (modulo 3) and digits d = 2 (modulo 3). It also cannot contain exactly three digits d = 1 or 2 (modulo 3). The largest possible solution has 3 digits, with one digit = 3, and the other two being equal (modulo 3). This case includes b = 10 (decimal numbers), so four or more digit solutions are impossible.

If b = 6k + 2, then for x = de we have x modulo 3 = (e - d) modulo 3. Therefore a solution x cannot have two digits that are the same (modulo 3). The largest possible solution has 3 different digits, with the first or the last digit = 3, and the other two being different (modulo 3).

The remaining case is b = 6k, where we can have at most three 1s, plus one of each prime < b. A digit 2 or 3 would have to be the first digit because d2 is divisible by 2 and d3 is divisible by 3 for any digit d. The number of digits in a solution x is therefore strongly limited, but I can't find any simple evidence that limits the number of digits.

In practice, if you take a five digit number x, there are ten 2-digit numbers, ten 3 digit numbers, five 4 digit numbers and one 5 digit number that would have to be primes, which is quite unlikely. And as the base b gets bigger, it gets more unlikely to find that many primes.

PS. I wrote a program systematically examining bases b up to about 4,000. There are thousands of four digit solutions. I found two five digit solutions: In base 12, 511b7 (b = 11) is a prime, and removing any digit or digits leaves a prime or the digit one. And in base 2730, the same for the five digit number (1)(1)(1423)(829)(631).

It looks like in base 2730 = 2 * 3 * 5 * 7 * 13, numbers where the last digit is a prime are primes much more often than in other bases.

Since a six digit solution requires several five digit solutions (at least four if the six digit solutions has three 1s and more if there are fewer 1s) for the same base b, and I found only two five digit solutions in total, a solution would be hard to find.

It's easy to show that if b is not a multiple of five, then for every six digit number x, that number or one of the numbers created by removing one to four digits is divisible by five. So to find a six digit solution, the base b must be a multiple of 30.

The chance that a random number x is prime is about 1 / ln x. But if we know that x is not divisible by 2, 3, or 5, then the chance is 3.75 / ln x. For x to be a six digit solution, the number x, plus six 5-digit, fifteen 4 digit, twenty 3-digit and fifteen 2-digit numbers must be prime. If we pick x where no digit is 2, 3, or 5, the chances for all these numbers to be prime is

$3.75^{57} / (ln p^6) / (ln p^5)^6 / ... / (ln p^2)^{15})$

or

$(3.75/ ln p)^{57} / (6 * 5^6 * 4^{15} * 3^{20} * 2^{15})$

On the other hand, the number of six digit numbers with all digits prime is about $(p / ln p)^6$. We can expect one solution x if the product is about 1. That's the case if the base is about b = 3.5 x $10^{15}$. At that point there are about $10^{85}$ six digit base-p numbers with all digits primes or 1. I don't think such a solution will ever be found.

$\endgroup$
  • $\begingroup$ In a base divisible by $2 \times 3 \times 5 \times 7 \times 13$, if the last digit is a prime other than $2, 3, 5, 7$ or $13$, you don't need to worry about divisibility by $2$, $3$, $5$, $7$ or $13$; that rules out a lot of composites... $\endgroup$ – Robert Israel May 6 '16 at 22:13
  • $\begingroup$ Good, but you probably shouldn't use $b$ for both an odd digit and the base. $\endgroup$ – dejongbrent May 7 '16 at 20:20

protected by Zev Chonoles May 4 '16 at 3:58

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.