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

Question

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.

Answer 1

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$

Answer 2

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.