[math-fun] prime ladders
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime. Example: 101 into 997: 101 -> 107 -> 197 -> 997 Challenge: Change 1009 into 9973. Rich
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009 Warut On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Do the rules permit you to go from 3 to 13? If yes, then I conjecture you can get from any prime to any other prime. On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
3 -> 13: My notion was that leading 0s are ruled out, so each size is a separate problem space. With this restriction, I think all the two digit primes are connected, and all the three digit primes are connected. The average number of connections is bounded, so there should be a few islands among the larger primes. The situation is interesting for other radices: Binary just barely hangs together for 5-7, is split for 11,13, and has a stringy graph for 17...29. Ternary (and other odd radices) split into disconnected pieces, based on the pattern of even and odd digits. If we allow leading 0s, I'd tend to agree with ACW, but consider one piece of contrary evidence: There's a five-digit number N such that N + 2^K is always composite. Rich -------------- Quoting Allan Wechsler <acwacw@gmail.com>:
Do the rules permit you to go from 3 to 13? If yes, then I conjecture you can get from any prime to any other prime.
On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I found that all the 4-digit primes are connected even under the restriction, and this is also true for the 5-digit case. Too lazy for larger cases ... Warut On Tue, Mar 10, 2009 at 11:41 PM, <rcs@xmission.com> wrote:
3 -> 13: My notion was that leading 0s are ruled out, so each size is a separate problem space. With this restriction, I think all the two digit primes are connected, and all the three digit primes are connected. The average number of connections is bounded, so there should be a few islands among the larger primes.
The situation is interesting for other radices: Binary just barely hangs together for 5-7, is split for 11,13, and has a stringy graph for 17...29.
Ternary (and other odd radices) split into disconnected pieces, based on the pattern of even and odd digits.
If we allow leading 0s, I'd tend to agree with ACW, but consider one piece of contrary evidence: There's a five-digit number N such that N + 2^K is always composite.
Rich
--------------
Quoting Allan Wechsler <acwacw@gmail.com>:
Do the rules permit you to go from 3 to 13? If yes, then I conjecture you can get from any prime to any other prime.
On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You can also make prime circles: I find that the graphs of k-digit primes are not only connected, but are Hamiltonian for k = 1,2 and 3. I haven't tried k = 4 yet. --nor have I tried for bases other than 10. Here are the Hamiltonian cycles for each of these cases: [2, 3, 5, 7, 2] [11, 13, 17, 19, 29, 23, 43, 53, 59, 79, 89, 83, 73, 71, 31, 37, 47,97, 67, 61, 41, 11] [101, 103, 503, 523, 223, 823, 863, 163, 563, 593, 193, 293, 263, 269, 569, 509, 409, 809, 109, 709, 701, 401, 601, 661, 461, 761, 769, 739, 439, 839, 139, 239, 229, 227, 257, 457, 557, 587, 547, 541, 241, 941, 641, 691, 191, 991, 997, 977, 971, 911, 211, 811, 311, 331, 631, 131, 431, 491, 421, 521, 571, 271, 277, 877, 577, 677, 647, 347, 947, 967, 937, 337, 367, 307, 907, 107, 607, 617, 317, 397, 797, 757, 157, 857, 887, 883, 283, 983, 683, 613, 673, 773, 743, 733, 233, 433, 463, 443, 643, 653, 953, 353, 853, 859, 829, 929, 919, 419, 719, 619, 659, 359, 349, 149, 179, 173, 113, 313, 373, 383, 389, 379, 479, 449, 499, 599, 199, 197, 137, 167, 467, 487, 787, 727, 127, 827, 821, 881, 281, 251, 751, 151, 181, 101] --Edwin On Wed, 11 Mar 2009, Warut Roonguthai wrote:
I found that all the 4-digit primes are connected even under the restriction, and this is also true for the 5-digit case.
Too lazy for larger cases ...
Warut
On Tue, Mar 10, 2009 at 11:41 PM, <rcs@xmission.com> wrote:
3 -> 13: My notion was that leading 0s are ruled out, so each size is a separate problem space. With this restriction, I think all the two digit primes are connected, and all the three digit primes are connected. The average number of connections is bounded, so there should be a few islands among the larger primes.
The situation is interesting for other radices: Binary just barely hangs together for 5-7, is split for 11,13, and has a stringy graph for 17...29.
Ternary (and other odd radices) split into disconnected pieces, based on the pattern of even and odd digits.
If we allow leading 0s, I'd tend to agree with ACW, but consider one piece of contrary evidence: There's a five-digit number N such that N + 2^K is always composite.
Rich
--------------
Quoting Allan Wechsler <acwacw@gmail.com>:
Do the rules permit you to go from 3 to 13? If yes, then I conjecture you can get from any prime to any other prime.
On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There exists no Hamiltonian cycle for 4-digit primes because 6983 is connected only to 6883. Similarly, there is no Hamiltonian cycle for 5-digit primes because 46769 is connected only to 96769. There is no Hamiltonian cycle for 6-digit primes because there is a 6-digit weakly prime. Warut On Thu, Mar 12, 2009 at 1:40 PM, Edwin Clark <eclark@math.usf.edu> wrote:
You can also make prime circles:
I find that the graphs of k-digit primes are not only connected, but are Hamiltonian for k = 1,2 and 3. I haven't tried k = 4 yet. --nor have I tried for bases other than 10.
Here are the Hamiltonian cycles for each of these cases:
[2, 3, 5, 7, 2]
[11, 13, 17, 19, 29, 23, 43, 53, 59, 79, 89, 83, 73, 71, 31, 37, 47,97, 67, 61, 41, 11]
[101, 103, 503, 523, 223, 823, 863, 163, 563, 593, 193, 293, 263, 269, 569, 509, 409, 809, 109, 709, 701, 401, 601, 661, 461, 761, 769, 739, 439, 839, 139, 239, 229, 227, 257, 457, 557, 587, 547, 541, 241, 941, 641, 691, 191, 991, 997, 977, 971, 911, 211, 811, 311, 331, 631, 131, 431, 491, 421, 521, 571, 271, 277, 877, 577, 677, 647, 347, 947, 967, 937, 337, 367, 307, 907, 107, 607, 617, 317, 397, 797, 757, 157, 857, 887, 883, 283, 983, 683, 613, 673, 773, 743, 733, 233, 433, 463, 443, 643, 653, 953, 353, 853, 859, 829, 929, 919, 419, 719, 619, 659, 359, 349, 149, 179, 173, 113, 313, 373, 383, 389, 379, 479, 449, 499, 599, 199, 197, 137, 167, 467, 487, 787, 727, 127, 827, 821, 881, 281, 251, 751, 151, 181, 101]
--Edwin
On Wed, 11 Mar 2009, Warut Roonguthai wrote:
I found that all the 4-digit primes are connected even under the restriction, and this is also true for the 5-digit case.
Too lazy for larger cases ...
Warut
On Tue, Mar 10, 2009 at 11:41 PM, <rcs@xmission.com> wrote:
3 -> 13: My notion was that leading 0s are ruled out, so each size is a separate problem space. With this restriction, I think all the two digit primes are connected, and all the three digit primes are connected. The average number of connections is bounded, so there should be a few islands among the larger primes.
The situation is interesting for other radices: Binary just barely hangs together for 5-7, is split for 11,13, and has a stringy graph for 17...29.
Ternary (and other odd radices) split into disconnected pieces, based on the pattern of even and odd digits.
If we allow leading 0s, I'd tend to agree with ACW, but consider one piece of contrary evidence: There's a five-digit number N such that N + 2^K is always composite.
Rich
--------------
Quoting Allan Wechsler <acwacw@gmail.com>:
Do the rules permit you to go from 3 to 13? If yes, then I conjecture you can get from any prime to any other prime.
On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, 11 Mar 2009, Warut Roonguthai wrote:
I found that all the 4-digit primes are connected even under the restriction, and this is also true for the 5-digit case.
Too lazy for larger cases ...
Warut
Also being lazy, but having no free will, I found the connected components of the 6-digit primes and the 7-digit primes. (primes p and q are adjacent if they differ in one digit); For the 6 digit primes there are 7 connected components: Six singletons corresponding to the 6 weak primes: 294001, 505447, 584141, 604171, 929573, 971767 and one large component containing the rest. For the 7-digit primes there are 38 connected components: 37 singletons corresponding to the 37 weak primes: 1062599, 1282529, 1524181, 2017963, 2474431, 2690201, 3070663, 3085553, 3326489, 4393139, 5152507, 5285767, 5564453, 5575259, 5974249, 6173731, 6191371, 6236179, 6463267, 6712591, 7204777, 7469789, 7469797, 7810223, 7858771, 7982543, 8090057, 8353427, 8532761, 8639089, 9016079, 9262697, 9537371, 9608189, 9663683, 9700429, 9931447 and one large component containing the rest. --Edwin PS I have submitted the 4 sequences suggested by Neil for this problem to the OEIS as A158576-A158579
Even relaxing the adjacency definition to allow 3-->31 and 3-->13, etc, the graph of all primes will not be connected: If you change any digit of the prime 971767 it becomes composite. Also if d > 0 is a digit then all integers of the form d971767 and of the form 971767d are composite. Edwin On Tue, 10 Mar 2009, rcs@xmission.com wrote:
3 -> 13: My notion was that leading 0s are ruled out, so each size is a separate problem space. With this restriction, I think all the two digit primes are connected, and all the three digit primes are connected. The average number of connections is bounded, so there should be a few islands among the larger primes.
The situation is interesting for other radices: Binary just barely hangs together for 5-7, is split for 11,13, and has a stringy graph for 17...29.
Ternary (and other odd radices) split into disconnected pieces, based on the pattern of even and odd digits.
If we allow leading 0s, I'd tend to agree with ACW, but consider one piece of contrary evidence: There's a five-digit number N such that N + 2^K is always composite.
Rich
--------------
Quoting Allan Wechsler <acwacw@gmail.com>:
Do the rules permit you to go from 3 to 13? If yes, then I conjecture you can get from any prime to any other prime.
On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009 9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
However, 10000971767 is prime. And I admit that it wasn't obvious from my earlier post that I was proposing allowing _any_ leading zero to mutate, that is in fact what I had in mind. It doesn't surprise me that there are islands under the rule Edwin Clark (naturally) read me as proposing. I think Rich Schroeppel understood what I meant, because (a) he knows how I think, and (b) he would agree that it's only infinite connectivity that rescues this graph from utter severage. On Thu, Mar 12, 2009 at 6:18 PM, Edwin Clark <eclark@math.usf.edu> wrote:
Even relaxing the adjacency definition to allow 3-->31 and 3-->13, etc, the graph of all primes will not be connected:
If you change any digit of the prime 971767 it becomes composite. Also if d
0 is a digit then all integers of the form d971767 and of the form 971767d are composite.
Edwin
On Tue, 10 Mar 2009, rcs@xmission.com wrote:
3 -> 13:
My notion was that leading 0s are ruled out, so each size is a separate problem space. With this restriction, I think all the two digit primes are connected, and all the three digit primes are connected. The average number of connections is bounded, so there should be a few islands among the larger primes.
The situation is interesting for other radices: Binary just barely hangs together for 5-7, is split for 11,13, and has a stringy graph for 17...29.
Ternary (and other odd radices) split into disconnected pieces, based on the pattern of even and odd digits.
If we allow leading 0s, I'd tend to agree with ACW, but consider one piece of contrary evidence: There's a five-digit number N such that N + 2^K is always composite.
Rich
--------------
Quoting Allan Wechsler <acwacw@gmail.com>:
Do the rules permit you to go from 3 to 13? If yes, then I conjecture
you can get from any prime to any other prime.
On Mon, Mar 9, 2009 at 1:11 AM, Warut Roonguthai <warut822@gmail.com> wrote:
9973 -> 1973 -> 1913 -> 1013 -> 1019 -> 1009
9973 -> 1973 -> 1933 -> 1033 -> 1039 -> 1009 9973 -> 1973 -> 1979 -> 1949 -> 1049 -> 1009 9973 -> 9173 -> 9103 -> 1103 -> 1109 -> 1009 9973 -> 9173 -> 9103 -> 9109 -> 1109 -> 1009
Warut
On Mon, Mar 9, 2009 at 10:30 AM, <rcs@xmission.com> wrote:
The Prime Ladder puzzle is to change one prime into another, by changing a digit at a time. All the intermediate numbers must also be prime.
Example: 101 into 997: 101 -> 107 -> 197 -> 997
Challenge: Change 1009 into 9973.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, 12 Mar 2009, Allan Wechsler wrote:
However, 10000971767 is prime.
Allan, Okay, now I see what you and Rich were getting at--especially Rich's comment that we know integers k such that k + 2^n is composite for nonnegative n. After searching for such numbers myself I finally found a few candidates which led me via online search to various results about Sierpinski numbers (k for which k*2^n + 1 are always composite) and their "duals" (k for which 2^n + k are always composite). No doubt this is what Rich was referring to. To account for changes in the binary representation of 1 to 0 it would be nice to also have the condition that k - 2^n is composite. Clearly both conditions k + 2^n and k - 2^n composite for all n together is much stronger than the differ-in-one-bit criterion. According to http://www.research.att.com/~njas/sequences/A076336 the Sierpinski numbers are conjectured to be the same as the dual Sierpinski numbers. (See comments about S1 and S2 in A076336.) Assuming this conjecture is true and checking the values given in A076336 the only prime in the OEIS list which "works", i.e., is isolated, (if I haven't made an error) is 2131099: That is, assuming this is a dual Sierpinski number one only needs to check that if any 1 digit is replaced by 0 in its binary representation then the corresponding value is composite. This seems to be the case. So assuming the conjecture that 2131099 is a dual Sierpinski number then it is an isolated vertex in the binary version of Rich's graph with Allan's extended definition of adjacency. Meanwhile I also found a paper by Yong-Gao Chen ,J. Number Theory 125 (2007), no.1, 14-15, wherein he apparently proves among other things that there exists an infinite arithmetic progression of positive odd integers k such that for any nonnegative integer n each of the four integers k-2^n,k+2^n,k2^n+1,k2^n-1 has at least two distinct odd prime factors. I glanced at the paper and so far as I can tell there is no evidence that the arithmetic progression he mentions contains a prime. Nevertheless one is encouraged to imagine that there is such a k that is prime. If so it would a fortiori be isolated in the binary version of Rich's graph with Allan's extension. Perhaps a base b Chen/Sierpinski-like number is too much to ask for? Namely, for base b >1 are there (hopefully prime) k such that k+a*b^n , k-a*b^n , k*b^n +a and k*b^n-a are composite for all n and positive a < b? This would give us isolated vertices for base b. A cursory search of MathSciNet didn't bring up any such stuff. Maybe someone knows more about such matters? A quick search found a few primes p such that for n from 0 to 20 and a from 1 to 9, p+a*10^n is composite. As things go in the Sierpinski -number-search-world this is very weak evidence, but suggestive enough for me to bet ( a small amount) on the graph having isolated vertices for all bases. Of course, it is trivial to find primes p such that p + 10^n is composite for all nonnegative integers n. For example, just choose p = 8 (mod 9). --Edwin
Yong-Gao Chen informed me of the paper by F. Cohen and J. L. Selfridge, "Not every number is the sum or difference of two prime powers", Math. Comp. 29(1975), 79-81 where one finds: COROLLARY 47867742232066880047611079 is prime and neither the sum nor difference of a power of two and a prime. If p is the prime in this corollary we have for all powers 2^n the numbers 2^n + p and p - 2^n must be composite. So p will be isolated in the base 2 version of the graph on primes. Yong-Gao also says that the conjecture:
For each "base" b > 1 there is a positive integer (hopefully a prime) k such that for all positive d < b and for all nonnegative n, the numbers k + d*b^n and k - d*b^n are composite.
follows from a well-known conjecture of Erdos: "There are covering systems with arbitrarily large least modulous." Yong-Gao says that the conjecture is not easy, but he thinks he can prove it for small b. Say b = 3 and 4. Not so sure whether he can do b = 10. --Edwin
Edwin wrote:
Even relaxing the adjacency definition to allow 3-->31 and 3-->13, etc, the graph of all primes will not be connected:
If you change any digit of the prime 971767 it becomes composite. ...
Yep, according to http://mathworld.wolfram.com/WeaklyPrime.html such numbers are said to be "weakly" prime. According to my code, the first 6 such numbers are: 294001 505447 584141 604171 929573 971767 Note that 929573 is missing from the above MathWorld page. Some more info about prime ladders: 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 Rich gave the challenge of turning 1009 into 9973, and Warut found a few 6-number solutions. A slightly longer solution is needed to turn 1009 into 9227: 1009 1109 7109 7129 7127 9127 9227 Andrew
On Fri, 13 Mar 2009, Andrew Trevorrow wrote:
Note that 929573 is missing from the above MathWorld page.
Perhaps since replacing the leading 9 by 0 gives a prime? PS Once again I missed an opportunity to find the weak prime concept. A simple search in the OEIS on the number 971767 brings up the sequence: http://www.research.att.com/~njas/sequences/A050249 --Edwin
participants (5)
-
Allan Wechsler -
Andrew Trevorrow -
Edwin Clark -
rcs@xmission.com -
Warut Roonguthai