# How would you prove that there is only a finite number of these primes?

For the purpose of this question you can assume/consider number $1$ to be a prime number, but the final result should not depend on that, that is, that there is only a finite number of primes like the one I found.

I was trying by pure guesswork and help from Wolfram Alpha to find as large as I can a prime number such that the process of removing digit by digit gives us again prime numbers.

I found not so large a prime that does the job.

It is $12373$. If we remove rightmost $3$ we obtain $1237$, a prime. Then removal of $2$ gives us $137$, a prime. Then removal of $3$ gives us $17$, a prime, and finally, removal of $1$ gives us $7$, a prime.

It is so natural to expect that there is a finite number of primes like $12373$, because, it is to be expected that after some number of removals we will hit a multiple of $3$, for example.

And, the larger the prime from which we start, larger are the chances to obtain a composite number after some number of steps because the number of steps to arrive at a single-digit prime for larger primes is larger.

I also believe that the number of such primes is "so small" that all of them can be found with the help of a computer.

How would you prove that there is only a finite number of such primes (like $12373$)?

EDIT: With the help of Barry (in his comment under a deleted answer) we now know that these are called deletable primes. On this linked page it is written that it is conjectured that there are an infinite number of such primes, while I conjectured here that there are only finitely many.

• It seems extremely difficult. At first glance, much harder than some problems that are still open. – ajotatxe Dec 28 '17 at 14:52
• See primes.utm.edu/glossary/xpage/DeletablePrime.html -- where it's said there are conjecturally infinitely many such primes. – Barry Cipra Dec 28 '17 at 15:00
• @Rohan, that's not a duplicate, because the condition there is that deleting any digit leaves a prime. – Barry Cipra Dec 28 '17 at 15:01
• I've tried this a bit and I found that 6166531357234211 satisfies this propriety. – Elie Louis Dec 28 '17 at 15:28
• Just a note: your number $12373$ has another sequence of primes. First remove the $2$ and you obtain $1373$. Then remove the first $3$ obtaining $173$. Now, no matter which number you remove you get a prime number. If you didn't remove the number $1$ in the previous step, remove it now (otherwise remove one of the two numbers) and you will end up with a prime number. – Batman Dec 28 '17 at 15:31

Take two bags of numbers. At the start, $A$ is empty and $B$ contains $2,3,5$ and $7$.

Repeat the following procedure:
Take a number, $p$, out of $B$ and put it in $A$. Then try all the possible ways to add one digit to $p$; and put all the primes you get into $B$.

It is likely to continue forever. The chance a number $N$ is prime, is around $\dfrac1{\ln N}$. The number of ways to add a digit is around $10\log_{10}N=(10\log_{10}e)\ln N$, so the average number of primes you put into bag $B$ for each $p$ you take out is $10\log_{10}e\approx 4.34$

• Vepir shows a greater increase than that. Most of the candidates end in 1,3,7 or 9, so are more likely than most numbers to be prime. – Michael Dec 28 '17 at 22:07

Consider the following construction:

We can go in reverse, and start constructing such examples by starting with a number, and inserting digits into it. If we get a prime, we can continue to add more digits. If not, we can try to add the digit at another place.

Edit: If we are also considering leading zeroes that get erased after truncating the first digit, we get few extra examples that weren't included in the previous construction.

I've found all of the examples for first few digit cases ;

Or to be more specific, if we look at such numbers with $d=2,3,4,5,6\dots$ digits, we have:

$$20 ,118 ,734 ,4679, 31722\dots$$

such prime numbers among $d$ digit numbers.

It would seem that this sequence would continue growing implying that there are infinitely many such prime numbers. But this does not need to be the case.

You can see the lists of all examples split into lists based on their length (digits) :

$d = 2$

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 97]

$d = 3$

[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 229, 233, 239, 241, 263, 269, 271, 283, 293, 307, 311, 313, 317, 331, 337, 347, 353, 359, 367, 373, 379, 383, 397, 401, 419, 421, 431, 433, 439, 443, 457, 461, 463, 467, 479, 487, 491, 503, 509, 523, 541, 547, 563, 569, 571, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 733, 739, 743, 751, 761, 769, 773, 797, 811, 823, 829, 839, 853, 859, 863, 883, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 997]

$d = 4$

[1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1123, 1151, 1153, 1163, 1181, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1277, 1279, 1283, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1427, 1429, 1433, 1439, 1451, 1459, 1481, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1549, 1567, 1571, 1579, 1597, 1601, 1607, 1609, 1613, 1619, 1627, 1637, 1657, 1663, 1667, 1693, 1697, 1699, 1709, 1723, 1733, 1753, 1759, 1783, 1789, 1801, 1811, 1823, 1831, 1861, 1867, 1871, 1873, 1879, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2029, 2039, 2053, 2063, 2069, 2083, 2111, 2113, 2129, 2131, 2137, 2141, 2161, 2179, 2203, 2213, 2237, 2239, 2243, 2269, 2273, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2371, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2441, 2467, 2503, 2539, 2593, 2609, 2617, 2633, 2647, 2659, 2663, 2671, 2677, 2683, 2689, 2693, 2699, 2711, 2713, 2719, 2729, 2731, 2741, 2791, 2797, 2803, 2833, 2837, 2843, 2903, 2939, 2953, 2963, 2969, 2971, 3001, 3011, 3019, 3023, 3037, 3041, 3061, 3067, 3079, 3083, 3109, 3119, 3121, 3137, 3163, 3167, 3181, 3187, 3191, 3217, 3229, 3253, 3259, 3271, 3301, 3307, 3313, 3319, 3331, 3347, 3359, 3361, 3371, 3373, 3391, 3407, 3413, 3433, 3457, 3461, 3463, 3467, 3491, 3511, 3517, 3529, 3533, 3539, 3541, 3547, 3559, 3571, 3583, 3593, 3607, 3613, 3617, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3823, 3833, 3847, 3853, 3863, 3907, 3911, 3917, 3919, 3929, 3931, 3947, 3967, 4001, 4003, 4007, 4013, 4019, 4021, 4051, 4057, 4073, 4079, 4091, 4127, 4129, 4133, 4139, 4157, 4159, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4261, 4271, 4283, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4421, 4423, 4457, 4463, 4483, 4493, 4507, 4517, 4519, 4523, 4547, 4561, 4567, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4651, 4657, 4663, 4673, 4679, 4691, 4721, 4729, 4733, 4751, 4759, 4787, 4789, 4793, 4799, 4801, 4817, 4831, 4861, 4871, 4877, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4987, 5003, 5009, 5011, 5023, 5039, 5059, 5099, 5101, 5107, 5113, 5147, 5167, 5171, 5179, 5197, 5209, 5231, 5233, 5237, 5273, 5303, 5309, 5323, 5347, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5471, 5477, 5479, 5503, 5563, 5569, 5623, 5639, 5641, 5647, 5653, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5741, 5743, 5791, 5839, 5869, 5903, 5923, 5939, 5953, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6091, 6101, 6113, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6211, 6217, 6229, 6247, 6263, 6269, 6271, 6277, 6301, 6311, 6317, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6397, 6421, 6427, 6451, 6473, 6481, 6491, 6529, 6547, 6553, 6563, 6569, 6571, 6577, 6599, 6607, 6619, 6653, 6659, 6661, 6673, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6791, 6793, 6803, 6823, 6829, 6833, 6841, 6863, 6883, 6907, 6911, 6917, 6947, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7039, 7043, 7069, 7079, 7103, 7109, 7127, 7129, 7151, 7159, 7193, 7211, 7219, 7229, 7243, 7283, 7297, 7307, 7309, 7331, 7333, 7349, 7351, 7369, 7393, 7433, 7451, 7457, 7487, 7517, 7523, 7541, 7547, 7561, 7573, 7591, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7691, 7699, 7703, 7723, 7753, 7793, 7823, 7829, 7853, 7873, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7951, 8011, 8017, 8039, 8053, 8059, 8101, 8111, 8117, 8123, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8389, 8419, 8423, 8429, 8431, 8443, 8461, 8467, 8513, 8537, 8539, 8543, 8563, 8573, 8597, 8599, 8623, 8629, 8641, 8647, 8663, 8677, 8693, 8719, 8753, 8761, 8783, 8803, 8831, 8837, 8839, 8863, 8893, 8923, 8929, 8941, 8963, 8971, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9059, 9067, 9103, 9109, 9127, 9137, 9151, 9157, 9161, 9173, 9181, 9199, 9209, 9239, 9241, 9277, 9283, 9293, 9311, 9319, 9337, 9341, 9371, 9377, 9397, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9533, 9539, 9547, 9601, 9613, 9619, 9629, 9631, 9643, 9661, 9677, 9679, 9697, 9719, 9721, 9733, 9739, 9743, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9829, 9833, 9839, 9859, 9871, 9883, 9907, 9929, 9941, 9967, 9973]

I can upload lists for $d\ge5$ if you want.

This does not answer your question as for an actual proof (disproof), this is still an open problem as Barry Cipra wrote in the comments.

Michael in his answer provides a reasoning of why this conjecture is likely to be true.

• Nice work, thank you. Now I do not know which side to choose, that there are finitely or infinitely many of them. – user480281 Dec 28 '17 at 16:48
• I ja sam iz Hrvatske. Haha. :) – user480281 Dec 28 '17 at 16:49
• @AntoinePalAdeen Haven't noticed. Svijet je malen :) – Vepir Dec 28 '17 at 16:55
• It occurs to me your procedure might miss some deletable primes. E.g., suppose $a0bc$ is prime with $bc$ deletable, but $abc$, $a0c$, and $a0b$ are not prime. Then you won't be able to construct $a0bc$, unless you (temporarily) consider $0bc$ to be a three-digit prime. And even if there's no such four-digit example, there could conceivably be one with more digits. – Barry Cipra Dec 28 '17 at 19:37
• Another observation: because the OP here is allowing $1$ as a starting point, the list here includes primes such as $109$ that are not in the sequence of deletable primes at oeis.org/A080608 -- but it's possible the two lists do agree beyond some number of digits. – Barry Cipra Dec 28 '17 at 21:14