Since Adam did most of the Mathematica work, I wrote the 5-minute program to just look for them: Neighbors[n_] := Flatten[MapIndexed[Table[n + (i - #) 10^(#2[[1]] - 1), {i, 0, 9}] &, Reverse[IntegerDigits[n, 10]]]] PrimeNeighbors[n_] := Complement[Select[Neighbors[n],PrimeQ],{n}] For[k=1, True, k++, If[ PrimeNeighbors[Prime[k]]=={}, Print["Isolated: ", Prime[k]]]] It takes about 5 seconds to produce 294001, 505447, 584141, 604171. Even the first term is enough to find http://oeis.org/A050249, "Weakly prime numbers (changing any one decimal digit always produces a composite number)." The OEIS has a link to the 2008 paper in which Terry Tao proved that for any base, a positive proportion of primes become composite after changing one digit. --Michael On Thu, Apr 30, 2015 at 12:27 PM, <rcs@xmission.com> wrote:
It fails for 4-bit binary primes.
The simplest heuristic argument seems to go the other way, suggesting the existence of isolated primes for large N. An N-digit prime has about 9N changes available. The (very naive) chance that any individual one of those is prime is 1/2.3N. So the chance that all 9N are composite is about e^-4, or 2%. So about 2% of the N-digit primes should be isolated. Since Adam has checked 3 & 4 digit primes -- 143 and ~1000, the 2% is way out of line. The first thing to fix is the units digit of N: This must be 1,3,7, or 9. If we change a non-units digit, the result will still end in 1,3,7, or 9, which boosts the chance of being prime by a factor of 2.5. This changes e^-4 into e^-10, around 1/20000. This resolves the 3 & 4 digit contradictions. But it hints that 6-digit primes (~70000) will have 3 or 4 singletons, and N>6 should always fail.
If you change the modification rule to "swap two digits", the large N stats become much more favorable. However, Dan Asimov & Neil Sloane once prodded me to look at numbers like 111111131111111111, and it turns out primes of that shape are (as expected) fairly thin, and swaps don't usually work.
Rich
--------
Quoting James Propp <jamespropp@gmail.com>:
Can anyone give a heuristic argument (based on the density of the primes
and their approximate independence from one another) that the property ought to hold for all sufficiently large n?
Jim Propp
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
_______________________________________________ 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.