Michael Kleber <kleber@brandeis.edu> writes:

No no no, these probabilistic arguments are going the wrong direction.

I figured out one reason last night, see below.

...

Let a prime be a good prime if a digit can be deleted leaving either=20=

...

the empty string or a good prime. Are there infinitely many good primes?

Let's be very naive and say that all we know is the prime number theorem, Pr(n is prime) =~ 1/ln(n).

Then E(# n-digit good primes) / E(# (n-1)-digit good primes) =~ (# ways to add a digit) * (Pr(an n-digit number is prime), which is around (10n) * (1/(n ln 10)) = 10/ln 10 =~ 4.34. So the number of good primes should grow exponentially.

That assumes that various n-1-digit primes you get have independent likelihood of being deletable. But that's not at all true, since if you have one n-1-digit delprime, then there is at least one n-2-digit delprime, and so the n-1-digit number you get from deleting the second digit first can be tranformed into the n-2-digit delprime by deleting a single digit. So the probabilities of getting delprimes by deleting different digits have a positive correlation. Looking at the sequence of deletions, I see that the case of divisibility by 3 is much different from what I had been thinking. The digits {1,4,7} and {2,5,8} must be deleted in alternation (possibly with intervening {0,3,6,9}s) or you will hit a number divisible by 3. In particular, the number of 1mod3 digits must differ from the number of 2mod3 digits by exactly 1. Dan Hoey@AIC.NRL.Navy.Mil