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

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

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

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

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

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