Don Reble <djr@nk.ca> writes:
Let p be a good prime if it has only one digit or else a single digit can be deleted leaving a prime.
Note that this definition was later amended. More below.
Sounds good to me. Indeed, a big prime may have a number of "shortened primes"; I wonder how many to expect.
Roughly, a number N has a 1/log(N) chance of being prime. That is, if a number has D digits, the odds are about log(10)/D = 2.302585/D.
If a number is prime, it's coprime to 10, at least, and so ends with 1, 3, 7, or 9. And "almost all" of the shortenings are also coprime to 10. The odds of being prime increase by a factor of almost 2.5.
So that's the product of 1 = probability of staying prime to 2 2 = relative density of primes in {1} mod 2 1 = probability of staying prime to 5 5/4 = relative density of primes in {1,2,3,4} mod 5 so 5/2 log(10)/D = 5.756463/D. In general, consider that we delete the k'th digit, b, from a D-digit prime P=a + b*10^k + (c*10^(k+1)), producing N = a + c*10^k = P - (b + 9*c)*10^k. For any a prime q, N==0 (mod q) iff P==(b+9c)10^k (mod q). I get Prob(N==0) (mod q) = 0 when q=2 or q=5, 3/10 when q=3, 1/q when q>5. So the probability that N is prime will be (Log(10)/D) Product (1 - Prob(q|N))/(1-1/q) (q prime) = (Log(10)/D) * (1/(1/2)) * ((7/10)/(2/3)) * (1/(4/5)) * ((1-1/q)/(1-1/q)) ^ whatever = (21/8) (Log(10)/D) = 6.044286/D .
Anyway, although the odds might not scale by 2.5, it comes awfully close: maybe 2.4971498... :-) So the primality-probability of a shortened prime is about 5.7499001/D.
Now, a (D+1)-digit prime has D+1 shortenings to D-digit numbers. You'd expect about 5.7499001*(D+1)/D primes among them. For large D, that approaches just 5.7499001.
One might imagine the distribution of prime shortenings to be Poisson. Therefore the probability that a big prime is _bad_ comes to exp(-5.7499001).
I think this should be 10^(-21/8) = .00237137. But the important thing is it's a constant. This is the probability that there is no way to remove a single digit and get a prime. But the intended definition was the probability we could remove a single digit and get a _good_ prime. If the probability of being able to remove a digit a second time were independent of the number of ways of removing the first digit, this would give a probability of .99762863^D that a prime would be good, and this would approach zero. In fact, we would expect a finite number of good primes. But to me it seems more likely that B(D), the probability of a D-digit prime being bad, might be (B(D-1))^((21/8) (Log(10)) = B(c) ^ (((21/8) Log(10))^(D-c)) which would make almost all large primes good. Dan