3 ms·

What if we allowed 0 as a digit? Are there infinitely many 0-enabled left-truncatable primes?

by jwilk 9y ago

ColinWright 9y ago
I would guess that there are infinitely many primes of the form 10^k+1. If so, that would be a yes.
- xelxebar 9y ago
  Actually, I believe this is an open problem at them moment. Primes of the form a^n + 1 are called Generalized Fermat Primes and the consensus seems to be that there are probably only finitely many for every base a.
- jwilk 9y ago
  But these truncate to 1, which is normally not considered prime.
  - ColinWright 9y ago
    Yah, I wrote that without thinking. Replace 1 with 3, and take a.10^k+p with p a small prime, etc.
svat 9y ago
Here is a heuristic argument for why we should expect there to be infinitely many. Suppose we start with a prime p which is d digits long (say p=3 so that d=1), and consider the sequence {a10^k + p : 1≤a≤9, k ≥ d}. So for p=3, we would consider 13, 23, … 93, then 103, 203, … 903, then 1003, 2003, … 9003, etc. By a standard heuristic argument (based on the prime number theorem), the number n is prime with "probability" about 1/log n, so each a10^k + p will be prime with probability about 1/k (ignoring some constant factors). The sum of these probabilities diverges, so one can be very confident that there will be a prime number in this sequence. In other words, we can be extremely confident of the following lemma: given any prime number p, there is a way of extending it to another prime number by adding some digit (followed by 0s) to its left. Repeated applications of this lemma (with any starting prime p, or even different primes p if you wish) will give the result. For example starting with the prime p=3 and taking the first choice each time, you get primes like 30007020009000000000000000600000000900906001600500006000001026001050612113. Of course, turning this heuristic argument from "extremely confident" to an actual proof is a challenge. (There may be ways to prove this, I don't know: I know this heuristic is often used by number theorists though.)

What if we allowed 0 as a digit? Are there infinitely many 0-enabled left-truncatable primes?

by jwilk 9y ago

What if we allowed 0 as a digit? Are there infinitely many 0-enabled left-truncatable primes?

ColinWright 9y ago

I would guess that there are infinitely many primes of the form 10^k+1. If so, that would be a yes.

xelxebar 9y ago
Actually, I believe this is an open problem at them moment. Primes of the form a^n + 1 are called Generalized Fermat Primes and the consensus seems to be that there are probably only finitely many for every base a.
jwilk 9y ago
But these truncate to 1, which is normally not considered prime.
- ColinWright 9y ago
  Yah, I wrote that without thinking. Replace 1 with 3, and take a.10^k+p with p a small prime, etc.

svat 9y ago

Here is a heuristic argument for why we should expect there to be infinitely many. Suppose we start with a prime p which is d digits long (say p=3 so that d=1), and consider the sequence {a10^k + p : 1≤a≤9, k ≥ d}. So for p=3, we would consider 13, 23, … 93, then 103, 203, … 903, then 1003, 2003, … 9003, etc. By a standard heuristic argument (based on the prime number theorem), the number n is prime with "probability" about 1/log n, so each a10^k + p will be prime with probability about 1/k (ignoring some constant factors). The sum of these probabilities diverges, so one can be very confident that there will be a prime number in this sequence. In other words, we can be extremely confident of the following lemma: given any prime number p, there is a way of extending it to another prime number by adding some digit (followed by 0s) to its left. Repeated applications of this lemma (with any starting prime p, or even different primes p if you wish) will give the result. For example starting with the prime p=3 and taking the first choice each time, you get primes like 30007020009000000000000000600000000900906001600500006000001026001050612113. Of course, turning this heuristic argument from "extremely confident" to an actual proof is a challenge. (There may be ways to prove this, I don't know: I know this heuristic is often used by number theorists though.)