I agree with Michael. It’s easy to check for smaller bases. For binary numbers 1/log(2) = 1.44 > 1 so there will still be a giant component. However, you get disconnected pieces starting at n=6. -Veit
On Apr 30, 2015, at 8:19 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
Hmm, I think I disagree with Adam, and that for large numbers of digits this should not happen.
As usual, I'll ignore "prime" and instead think about an arbitrary set of integers P such that n is a member of P with probability 1/log(n).
The number of neighbors of n in Jim's graph is around 9 * log_10(n). So the probability that none of them is prime is (1-1/log(n))^(9 log_10(n)), which for large n is exp(-9/log(10)), or around 2%.
For actual primes, surely things are not all independent, and things like restricted last digits will make it some other number. But it's still the case that the growing number of neighbors is offset by the falling probability of each being prime.
So I'd expect that there are isolated primes, which become non-prime when you change any digit, and indeed that they should tend towards being a nonzero fraction of all d-digit primes, for large d.
--Michael