[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
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
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
The average degree of the graph, for n-digit primes, should be 9n/(n log(10)) = 3.9 — more than enough for a random graph to have a giant component. I’ve checked it for n=5. -Veit
On Apr 30, 2015, at 8:09 AM, James Propp <jamespropp@gmail.com> wrote:
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?
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
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.
Note that this solves the simpler problem of detected isolated primes, which is sufficient but not necessary for determining that n-digit primes are not connected. In the general case, you have to consider the situation where there are multiple partitions for the n-digit primes, each of which contains more than one prime (i.e., none are isolated, but they are not connected). Tom Michael Kleber writes:
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I didn't word this very well. I should have said: ... which is a sufficient, but not necessary, condition for n-digit primes being disconnected. Tom Tom Karzes writes:
Note that this solves the simpler problem of detected isolated primes, which is sufficient but not necessary for determining that n-digit primes are not connected.
In the general case, you have to consider the situation where there are multiple partitions for the n-digit primes, each of which contains more than one prime (i.e., none are isolated, but they are not connected).
Tom
Michael Kleber writes:
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. _______________________________________________ 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
Right, there are lots of ways that the graph can be disconnected, with the existence of an n-digit "weakly prime" being only the simplest one. From the heuristic point of view, "weakly prime" is the most likely form of disconnection. But the same logic should lead to any fixed-sized isolated subgraph having positive probability. So "two primes connected to each other, but to nothing else" should also have a nonzero density. --Michael On Thu, Apr 30, 2015 at 1:35 PM, Tom Karzes <karzes@sonic.net> wrote:
I didn't word this very well. I should have said:
... which is a sufficient, but not necessary, condition for n-digit primes being disconnected.
Tom
Tom Karzes writes:
Note that this solves the simpler problem of detected isolated primes, which is sufficient but not necessary for determining that n-digit primes are not connected.
In the general case, you have to consider the situation where there are multiple partitions for the n-digit primes, each of which contains more than one prime (i.e., none are isolated, but they are not connected).
Tom
Michael Kleber writes:
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. _______________________________________________ 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.
Consider the following graph in 3-space: Start with a white rectangle, say [0,3] x [0,1]. Blacken the intervals {n} x [0,1] for n = 0, 1, 2, 3. Also blacken the edges {0} x [0,1} and {1} x [0,1]. Now identify (0,t) with (1,1-t) for all t in [0,1], et voilà: a Möbius band. Arrange this in space to be the usual picture of a Möbius band with one half-twist. Finally, delete everything that is not blackened, leaving a graph of 6 edges and 6 vertices with a particular embedding in 3-space. Call the abstract graph K, and its embedding in space the function h: K -> R^3. PUZZLE: ------- Can K be continuously manipulated through homeomorphic graphs in 3-space so that it coincides with its mirror image? (Or more formally: Is there a continuous mapping H: K x [0,1] -> R^3 such that a) H(x,0) = h(x), for all x in K; b) H restricted to K x {t} is an embedding into R^3, for all t in [0,1]; c) H restricted to K x {1} is an embedding into R^3 whose image is a mirror image K' of K ?) --Dan
Arrgh. Corrections:
On Apr 30, 2015, at 12:03 PM, Dan Asimov <asimov@msri.org> wrote:
Consider the following graph in 3-space:
Start with a white rectangle, say [0,3] x [0,1].
Blacken the intervals {n} x [0,1] for n = 0, 1, 2, 3.
Also blacken the edges {0} x [0,1} and {1} x [0,1].
Also blacken the edges [0,3] x {0} and [0,3] x {1}.
Now identify (0,t) with (1,1-t) for all t in [0,1], et voilà: a Möbius band.
Now identify (0,t) with (3,1-t) for all t in [0,1], et voilà: a Möbius band.
Arrange this surface in space to be the usual picture of a Möbius band with one half-twist.
Finally, delete everything that is not blackened, leaving a graph of 6 edges and 6 vertices with a particular embedding in 3-space.
Call the abstract graph K, and its embedding in space the function
h: K -> R^3.
PUZZLE: -------
Can K be continuously manipulated through homeomorphic graphs in 3-space so that it coincides with its mirror image?
(Or more formally: Is there a continuous mapping
H: K x [0,1] -> R^3
such that
a) H(x,0) = h(x), for all x in K;
b) H restricted to K x {t} is an embedding into R^3, for all t in [0,1];
c) H restricted to K x {1} is an embedding into R^3 whose image is a mirror image K' of K
?)
Once the dust settles, I would like to see the sequence that gives the number of components of the graph for primes of length n (in base 10, or any other small base)! Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Apr 30, 2015 at 2:08 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Right, there are lots of ways that the graph can be disconnected, with the existence of an n-digit "weakly prime" being only the simplest one. From the heuristic point of view, "weakly prime" is the most likely form of disconnection. But the same logic should lead to any fixed-sized isolated subgraph having positive probability. So "two primes connected to each other, but to nothing else" should also have a nonzero density.
--Michael
On Thu, Apr 30, 2015 at 1:35 PM, Tom Karzes <karzes@sonic.net> wrote:
I didn't word this very well. I should have said:
... which is a sufficient, but not necessary, condition for n-digit primes being disconnected.
Tom
Tom Karzes writes:
Note that this solves the simpler problem of detected isolated primes, which is sufficient but not necessary for determining that n-digit primes are not connected.
In the general case, you have to consider the situation where there are multiple partitions for the n-digit primes, each of which contains more than one prime (i.e., none are isolated, but they are not connected).
Tom
Michael Kleber writes:
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. _______________________________________________ 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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Michael Kleber wrote:
... It takes about 5 seconds to produce 294001, 505447, 584141, 604171.
Even the first term is enough to find http://oeis.org/A050249 ...
The full set of isolated 6-digit primes is 294001, 505447, 584141, 604171, 929573, 971767. Note that A050249 doesn't include 929573 because 029573 isn't prime. See http://oeis.org/A158124 for the sequence of isolated primes where the 1st digit can't be changed to 0. Many moons ago I wrote a small Mac app called Alchemy for finding word ladders. It lets you define the valid characters in a word, so by choosing 0..9 it's easy to create a "word" list containing prime numbers for finding prime ladders. The app also lets you find isolated primes, or search the shortest ladders for each pair of primes and find the longest examples: no. of digits: 2 3 4 5 6 longest ladder: 4 7 9 11 13 example: 23 389 2441 88259 440497 43 383 5441 88289 410497 47 883 5741 88789 416497 37 863 5701 88799 416477 463 3701 82799 416473 461 3709 12799 416873 761 3109 12791 406873 9109 92791 406883 9199 92761 706883 99761 705883 99721 705833 905833 995833 Sadly, Alchemy is so old it only runs on Mac OS 10.6 or older, but I hope to modernize it one day. (More details can be seen at http://www.trevorrow.com/alchemy/. If you do have an old Mac and want to play with Alchemy then let me know and I'll send you my Primes word list.) Andrew
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.
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
A quick Python hack says, for base=10 and n=6, there's no path connecting 100003 and 294001 (disallowing 0 as a leading digit for any intermediate values). Of couse, that's assuming I didn't make a mistake, so feel free to prove me wrong... Tom James Propp writes:
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
participants (9)
-
Adam P. Goucher -
Andrew Trevorrow -
Dan Asimov -
James Propp -
Michael Kleber -
Neil Sloane -
rcs＠xmission.com -
Tom Karzes -
Veit Elser