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 On Thu, Apr 30, 2015 at 10:12 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I conjecture it's true for all n (and verified for 3, 4 as well). Here's an app which allows you to see the graph of primes connected by single-digit replacements:
Manipulate[ GraphPlot3D[ Flatten[Map[ Function[{n}, Map[(n -> #) &, Select[Flatten[ MapIndexed[ Table[n + (i - #) 10^(#2[[1]] - 1), {i, # + 1, 9}] &, Reverse[IntegerDigits[n, 10]]]], PrimeQ]]], Select[Table[i, {i, 10^(digits - 1), 10^digits}], PrimeQ]]], VertexLabeling -> True], {{digits, 2}, 1, 4, 1}]
Sincerely,
Adam P. Goucher
Sent: Thursday, April 30, 2015 at 2:17 PM From: "James Propp" <jamespropp@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] Prime ladders
For what values of n is it possible to get from every n-digit prime number to every other by way of a succession of single-digit alterations?
It's trivially true for n=1, and it's also true for n=2 since every 2-digit prime remains prime if you change its first digit to a 1.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.