On the cardinality of certain set of primes?

Question

A prime number p with n digits is called an embedded prime if it remains prime after eliminating the leftmost i digits of p, for i = 0,...,n-1. For example:

137 is an embedded prime because
-137 is prime
-37 is prime
-7 is prime

or

45197 is an embedded prime because
-45197 is prime
-5197 is prime
-197 is prime
-97 is prime
-7 is prime

But, 4127 is not an embedded prime because
-4127 is prime
-127 is prime
-27 is NOT prime
-7 is prime

Is the set of all embedded primes infinite? If not, what is the largest embedded prime? If there is a largest, then since any n digit embedded prime is an extension of an n-1 digit embedded prime, this question seems suitable to be answered by a computer program. However, I have neither the means nor know-how to experiment.

The largest I have found so far is:

9997564326947

I used GAP, but seems to have trouble testing primality for 14 digit numbers, so I don't know where to go from here.

However, if you except GAP's use of the probablistic primality test, then I get as THE largest embedded prime the 16 digit:

3001635613269915683

The number of embedded primes of different sizes are given by:

1: 4
2: 11
3: 39
4: 99
5: 192
6: 326
7: 429
8: 521
9: 545
10: 517
11: 448
12: 354
13: 276
14: 212
15: 117
16: 362
17: 0

It is interesting how it increases until 9 digits and then decreases except for a last gasp at 16 digits.

I would appreciate if someone could reproduce my results.

Disregard the previous edit as there must have been something awfully wrong with the way I programmed (which is why I said earlier that I am without the know-how). There should be no zeroes anywhere in the number. My algorithm was supposed to take the list of all embedded primes with n-1 digits and append the digits 1-9 to the front of them, checking if they are still prime. If this is what the program was actually doing, there could never be a zero as a digit. I'll have to work on the programming aspect.

For the one who says that modern mathematics cannot answer my question, well maybe not if the answer is yes (and I doubt it is). But if the answer is no, I think a good programmer could solve it in less than 20 minutes with a reasonable language (like GAP or MAGMA) and sufficient computing power. If only there was someone in the Yahoo! Answers community who was a good programmer...

Okay, I think I have an answer now. Here is my new list of how many embedded primes exists for a given number of digits:

Digits #of embedded primes
1 4
2 11
3 39
4 99
5 192
6 326
7 429
8 521
9 545
10 517
11 448
12 354
13 276
14 212
15 117
16 72
17 42
18 24
19 13
20 6
21 5
22 4
23 3
24 1

and the magic number, the largest embedded prime is...

357686312646216567629137

I am still interested in independent confirmation.

Answer 1

You can find independent confirmation using Google here:

http://en.wikipedia.org/wiki/Truncatable_prime

here:

http://mathworld.wolfram.com/TruncatablePrime.html

and of course here:

http://www.google.com/search?q=357686312646216567629137&

(Just search for the number you found and it shows up all over as the largest left-truncatable prime.)

Answer 2

I'm certain that modern-day mathematics cannot answer your question. It's funny how easy it is to come up with "unsolvable" problems like this. Here's another one. Let f(x) be a polynomial with integer coefficients, and degree 2 or greater, that doesn't factor into other integer polynomails. Like x^3-x+1. Then noone will be able to tell you if there are infinitely many primes of that form with x an integer. If f has degree one, however, an amazing result called Dirichlet's Theorem on Primes in an Arithmetic Progression says that as long as the coefficients are relatively prime, there are infinitely many primes of that form. Interestingly enough, there's no formula for such primes. Project?

Just felt like sharing. Good luck!

Answer 3

What about cases where the value contains one or more 0s? For example, is 1013 an embedded prime? 1013 is prime, as are 13 and 3. If you accept 1013 as an embedded prime, then the problem can be expressed as proving the infinitude of primes of the form 10^n+m where m is an embedded prime with fewer than n digits.

Note: to fredorgeorge... - the set of all primes is easily provable as infinite.

Answer 4

It is true that any embedded prime is the extension of an n-1 embedded prime but that does not guarnatee that the next higher up does exist. According to Riemann's distribution, primes get scarcer as numbers get larger, although a computer is well suited to find out the answer, its the computing power which counts.

Answer 5

I don't know but I noticed the following:
the two big numbers that you gave have high incidences of 3,6,9 :
0(2), 1(3), 2(2), 4(2), 5(2), 7(2), 8(1)
and 3(5), 6(6), 9(6)
This is not a coincidence since, if we want to avoid divisibility by 3 we can add 3,6 or 9 to the previous number( who wasn't divisible by 3) in any step.
But if add 2, 5, 8( 2 modulo3) in one step , we can't add one of those numbers in the next step. The same for group 1, 4, 7(1 modulo 3).
( I don't give all details)

Answer 6

The set of all prime numbers is (presumably) finite, though we do not know what the highest prime number is, so we can not know the cardinality of this set. I do not know how you can make the transition to embedded primes, but you could set up some sort of computer program to work it out.

Answer 7

It will be infinite since each embedded prime is an extension. It will never end.