Problems & Puzzles: Puzzles

Puzzle 1132 The largest row of K distinct primes such that... Paul Lamford sent a puzzle similar to the finally written below after discussing with him certain changes: Process: Create a row of K distinct primes each one of them having the same quantity of k digits and such that for every two contiguous primes these just differ by one digit while all the others remain in their position. This process ends when you reach to an extreme prime than can not generate another prime not existing in the row. Example 1, (k=1, K=4) 2, 3, 5, 7. K=4 is the largest possible K for k=1. Example 2: (k=2, K=21) 97, 47, 37, 67, 61, 41, 31, 11, 13, 17, 19, 29, 23, 43, 73, 71, 79, 59, 53, 83, 89. K=21 is the largest possible K for k=2. Please notice that you can enlarge the row adding primes to the row by the leftmost &/or the rightmost prime of the row, as you wish. Q1. Send your largest row of K distinct prime for each k=3, 4, 5 & 6. Q2. Do you believe that for each k, is it possible to write down a row with the largest possible K of distinct primes for the given k, according to the process pointed out above? See A006879

---

From May 20 to May 26, contributions came from Michael Branicky, Giorgos Kalogeropoulos, Michael Hürter, Alessandro Casini, Claudio Meller, JM Rebert, Adam Stinchcombe, Emmanuel Vantieghem.

***

Branicky wrote:

Carlos, nice problem. Optimal solutions for k = 3 and 4 are below. I am working on 5 and 6.
Are you sure you want the answers for 5 and 6? They may be too long for email/posting.
Should I send a link to file(s)?


The problem involves finding longest paths in the graph P(k, 10), where the vertices are k-digit primes in base 10 and edges connect vertices with Hamming distance 1 (cf. OEIS A158576).


The graphs P(k, 10) for k = 3..6 have the following number of nodes (cf. OEIS A006879) and connected components (cf. OEIS A158576):
* P(3, 10): 143 nodes, 517 edges, 1 connected component;
* P(4, 10): 1061 nodes, 4107 edges, 1 connected component;
* P(5, 10): 8363 nodes, 33393 edges, 1 connected component;
* P(6, 10): 68906 nodes, 279563 edges, 1 connected component with 68900 nodes and 6 isolated nodes.


Below is an optimal longest path involving all 143 nodes in P(3, 10):
(k=3, K=143): 139, 199, 149, 179, 479, 439, 449, 499, 419, 409, 709, 509, 809, 109, 107, 197, 167, 127, 157, 137, 337, 367, 397, 317, 347, 307, 907, 937, 997, 977, 877, 577, 277, 677, 607, 617, 647, 947, 967, 467, 461, 491, 431, 421, 401, 601, 691, 661, 641, 631, 331, 131, 191, 991, 941, 971, 911, 311, 211, 271, 241, 281, 251, 257, 457, 857, 557, 757, 797, 727, 227, 827, 887, 787, 487, 587, 547, 541, 571, 521, 821, 811, 881, 181, 151, 751, 761, 701, 101, 103, 193, 163, 173, 113, 313, 613, 673, 643, 653, 683, 883, 383, 353, 853, 953, 983, 283, 293, 223, 263, 463, 443, 433, 233, 239, 839, 859, 829, 823, 863, 563, 523, 503, 593, 599, 569, 769, 269, 229, 929, 919, 719, 619, 659, 359, 349, 389, 379, 373, 773, 743, 733, 739


Below is an optimal longest path involving all 1061 nodes in P(4, 10):
(k=4, K=1061): 6983, 6883, 6833, 6803, 6863, 6823, 1823, 1523, 1723, 1123, 1223, 1229, 6229, 3229, 7229, 4229, 4129, 7129, 2129, 1129, 1429, 1423, 1483, 1493, 1453, 1459, 1499, 1489, 1439, 1433, 9433, 9833, 9533, 9133, 9733, 1733, 6733, 4733, 4723, 4703, 4793, 4783, 1783, 1583, 1283, 4283, 4583, 4483, 4493, 4093, 1093, 1033, 1013, 1063, 1061, 1069, 1019, 1049, 1039, 7039, 5039, 8039, 2039, 2069, 2029, 2099, 2089, 2689, 9689, 8689, 5689, 6689, 6089, 8089, 8389, 2389, 2789, 1789, 1289, 4289, 4789, 4729, 4799, 4099, 4019, 4049, 9049, 9649, 9949, 9349, 9749, 9743, 9043, 9643, 9343, 9341, 9041, 9001, 9091, 9011, 9013, 4013, 7013, 7019, 7069, 8069, 8969, 8669, 8629, 8429, 8929, 8329, 6329, 6389, 3389, 3089, 3049, 3041, 3001, 3061, 3011, 3019, 3079, 7079, 4079, 4073, 4003, 4903, 4993, 4999, 8999, 8699, 2699, 2999, 1999, 1699, 1697, 1657, 1627, 1637, 1607, 1667, 1669, 1663, 1693, 1193, 1163, 1153, 1753, 1759, 4759, 4259, 1259, 1559, 1553, 1543, 1549, 1949, 1249, 1279, 1979, 1579, 1879, 1889, 4889, 3889, 3989, 3929, 3329, 3319, 3919, 3119, 3719, 9719, 9769, 9739, 9839, 9539, 9239, 9439, 9431, 9491, 9791, 9391, 9311, 9319, 9619, 9629, 9929, 9029, 6029, 6079, 6679, 9679, 9479, 9419, 9413, 9403, 9473, 9173, 9973, 4973, 4933, 4943, 4243, 4253, 4273, 4673, 4643, 4603, 4663, 8663, 8693, 8093, 8293, 8893, 8803, 9803, 9203, 9103, 1103, 7103, 7703, 6703, 6763, 6163, 6173, 6673, 6073, 6473, 6373, 4373, 3373, 1373, 1873, 1973, 1993, 7993, 7193, 7793, 6793, 3793, 3733, 3739, 3769, 3779, 6779, 6379, 6359, 3359, 3259, 3559, 3539, 3529, 6529, 7529, 7559, 7549, 7589, 7789, 7759, 7753, 7723, 7823, 3823, 3803, 3833, 2833, 2803, 2903, 2203, 2503, 2003, 2063, 2963, 2663, 2693, 2593, 2293, 9293, 9283, 9883, 7883, 7283, 7583, 3583, 3593, 3533, 3433, 7433, 7933, 7963, 8963, 8863, 3863, 3853, 7853, 7253, 7243, 2243, 8243, 8263, 8273, 8233, 8933, 1933, 1931, 9931, 4931, 4951, 1951, 1901, 9901, 9941, 8941, 8951, 7951, 7901, 7001, 4001, 4091, 4051, 5051, 1051, 1031, 1231, 1831, 1871, 1801, 1811, 1861, 5861, 5851, 5801, 5881, 5821, 3821, 3121, 3221, 6221, 6121, 6521, 6421, 9421, 9221, 9721, 9521, 5521, 5021, 4021, 1021, 1091, 6091, 6791, 6991, 6691, 6491, 3491, 3691, 3191, 3391, 3301, 3361, 3331, 3371, 3271, 3671, 3673, 3643, 3623, 3323, 3923, 3943, 3343, 6343, 6353, 6323, 9323, 9923, 9623, 8623, 5623, 5323, 5923, 8923, 8123, 8423, 4423, 2423, 2473, 2273, 5273, 5233, 5231, 4231, 8231, 8237, 1237, 5237, 2237, 2239, 2539, 2339, 2939, 2969, 2269, 8269, 8369, 8363, 4363, 4463, 9463, 3463, 3163, 3169, 3469, 3461, 9461, 9467, 3467, 3767, 9767, 9967, 3967, 3917, 3947, 3907, 9907, 1907, 7907, 6907, 6967, 6917, 6947, 6977, 6997, 1997, 1097, 1597, 1297, 8297, 5297, 2297, 2207, 2267, 2767, 2467, 2437, 2477, 2447, 2417, 2917, 2617, 2647, 2657, 2677, 2687, 2683, 2633, 2333, 5333, 7333, 7393, 2393, 2383, 2083, 3083, 3023, 5023, 5003, 5903, 5303, 5503, 5501, 5581, 5531, 1531, 1571, 3571, 3581, 3181, 3881, 3851, 3251, 3253, 3257, 3217, 3517, 3617, 3677, 9677, 9697, 3697, 3637, 3607, 3407, 3457, 3557, 2557, 2957, 4957, 4937, 4967, 4969, 4919, 4219, 7219, 7919, 7949, 6949, 6959, 6659, 3659, 2659, 2459, 7459, 7489, 7499, 7699, 7669, 5669, 5659, 5657, 4657, 4457, 7457, 7451, 4451, 4421, 4481, 6481, 6451, 1451, 1151, 7151, 7159, 4159, 4157, 4153, 4133, 6133, 6113, 6143, 6043, 7043, 7643, 7649, 7639, 5639, 5939, 5839, 8839, 8539, 8599, 8597, 8537, 8837, 8831, 4831, 4801, 4861, 4871, 4271, 4201, 4211, 4217, 4297, 7297, 7237, 7247, 7207, 7507, 5507, 5557, 5857, 2857, 2357, 4357, 4057, 4007, 4507, 4517, 4597, 4397, 6397, 9397, 9497, 9437, 5437, 5407, 5417, 7417, 7517, 7547, 4547, 3547, 3527, 3727, 3797, 2797, 2707, 2777, 2377, 2347, 3347, 3307, 7307, 1307, 1303, 1301, 1361, 1321, 1381, 1181, 1171, 1471, 1481, 1487, 1987, 1787, 1187, 1087, 2087, 2887, 2287, 8287, 8087, 8387, 8887, 9887, 9857, 9817, 9811, 9851, 9871, 9371, 2371, 2381, 2341, 2311, 2351, 2851, 2801, 2861, 8861, 8461, 8467, 8867, 8807, 5807, 5867, 5869, 5879, 5279, 5479, 5477, 5077, 5087, 5081, 5011, 6011, 2011, 8011, 8081, 2081, 2281, 2251, 2221, 8221, 8821, 8521, 2521, 2551, 2531, 2591, 2791, 2741, 8741, 7741, 1741, 1721, 4721, 4751, 4651, 5651, 5653, 5153, 5953, 2953, 2053, 2153, 2143, 2843, 2543, 2549, 2749, 2729, 2719, 8719, 8779, 5779, 5749, 5741, 5791, 5591, 4591, 4391, 4691, 4621, 1621, 2621, 2671, 2971, 6971, 8971, 8171, 8161, 8761, 3761, 3701, 5701, 5711, 2711, 2411, 2111, 4111, 8111, 8311, 6311, 6211, 6271, 6871, 6841, 7841, 7541, 3541, 3511, 1511, 9511, 9551, 9151, 6151, 6551, 6581, 8581, 8501, 8101, 8191, 8291, 1291, 1201, 1601, 1609, 1009, 1109, 7109, 3109, 3709, 1709, 1409, 4409, 4909, 2909, 2609, 8609, 8009, 5009, 5099, 5059, 8059, 9059, 9859, 9829, 6829, 7829, 7879, 7873, 7673, 7603, 7607, 6607, 6637, 4637, 4337, 4327, 4127, 4027, 2027, 2017, 8017, 8317, 6317, 6217, 1217, 1117, 8117, 8167, 3167, 3067, 9067, 9007, 6007, 6067, 6367, 6337, 9337, 9377, 8377, 8677, 8627, 8527, 5527, 5827, 5897, 2897, 2837, 2137, 9137, 9157, 9187, 3187, 3137, 3037, 6037, 6047, 6247, 6287, 6277, 1277, 9277, 9257, 6257, 6857, 6827, 6427, 1427, 1327, 1367, 1867, 1567, 4567, 4561, 7561, 7591, 7691, 7621, 7121, 7321, 7331, 7351, 5351, 5381, 5981, 5281, 5261, 4261, 4241, 9241, 9281, 9181, 9781, 6781, 6761, 6361, 6661, 6961, 6911, 3911, 3931, 3631, 9631, 9601, 9661, 9161, 2161, 2141, 2441, 4441, 4447, 1447, 8447, 8647, 8147, 8747, 8707, 8737, 6737, 5737, 5717, 7717, 7727, 7757, 7057, 7027, 7127, 9127, 9227, 5227, 5927, 2927, 7927, 7937, 7537, 7577, 7477, 7487, 7481, 7411, 7211, 7213, 2213, 1213, 1913, 1613, 9613, 3613, 3313, 3413, 5413, 5419, 8419, 8219, 8209, 3209, 3203, 6203, 6263, 6269, 6869, 6469, 6569, 6599, 6899, 6299, 3299, 3499, 3449, 6449, 5449, 5849, 8849, 8819, 2819, 2879, 2579, 2179, 8179, 5179, 5189, 5119, 5113, 2113, 2713, 2753, 8753, 8353, 8053, 6053, 6653, 6553, 6563, 8563, 5563, 5569, 5519, 4519, 4549, 4649, 4679, 4639, 4139, 4339, 4349, 7349, 7369, 7309, 2309, 2399, 1399, 1319, 1619, 6619, 6719, 6709, 6701, 6301, 6101, 6131, 2131, 2731, 8731, 8431, 5431, 5441, 5471, 5171, 5101, 5107, 5167, 5197, 6197, 6199, 9199, 9109, 9209, 5209, 5309, 5399, 5393, 5693, 5683, 5483, 5443, 8443, 8543, 8573, 5573, 7573, 7523, 4523, 4513, 8513, 8713, 8783, 5783, 5743, 5843, 5813, 4813, 4817, 7817, 7867, 7877, 1877, 1777, 1747, 1847, 3847, 3877, 4877, 4177, 7177, 7187, 7687, 7681, 8681, 8641, 5641, 5647, 5147, 5347, 5387, 5987, 4987, 4787, 9787, 9587, 9547, 6547, 6577, 6571


Regarding Q2, the largest possible K is the length of the longest simple path (no vertices repeated) in P(n, 10). While computing this is NP-hard, it is well defined for all n.
....
I found a simple path in P(5, 10) with length 8283 (aka k=5, K=8283)....and a simple path in P(6, 10) with length 64306 (aka k=6, K=64306). These are the attached text files (k=5, k=6). Both are not the largest possible.

***

Giorgos wrote:

Q1:

(k=2, K=21) This is the largest possible and also cyclic (the last term can be joined with the first term)

{11,19,29,59,79,89,83,23,43,53,73,13,17,97,37,67,47,41,31,61,71}
 

 

(k=3, K=143) This is the largest possible and cyclic

{787,727,127,227,277,257,251,751,151,181,281,881,811,211,

241,271,571,541,521,523,823,223,229,929,919,911,971,941,

991,191,691,631,131,331,311,317,617,677,577,587,487,457,

557,547,347,647,947,977,877,827,821,829,859,853,883,983,

283,683,383,389,349,149,179,173,773,673,373,353,953,653,

659,359,379,479,449,443,463,863,163,563,569,769,709,109,

809,509,503,103,113,313,613,619,719,739,139,839,239,269,

263,233,293,193,593,599,199,499,409,419,439,433,733,743,

643,641,661,761,461,431,421,491,401,701,101,601,607,107,

907,307,337,137,937,967,167,467,367,397,997,197,797,757,

157,857,887}
 

 

(k=4, K=1061) This is the largest possible

{9497,9467,9967,3967,4967,4969,4909,4409,1409,1439,1429,

8429,8329,3329,3929,3229,3529,3527,3557,5557,2557,2957,

2357,2377,9377,9371,2371,2381,2341,2347,2447,2647,5647,

5657,5651,5851,5881,5081,5981,5581,5501,5521,5821,8821,

8861,8761,8161,8101,8111,4111,2111,2161,9161,9151,1151,

7151,7121,6121,3121,3181,9181,9781,9721,4721,4021,4027,

2027,2017,8017,8317,8117,1117,1217,3217,4217,4297,7297,

1297,8297,8287,2287,6287,6277,6577,6571,6271,6971,6911,

6917,6317,6217,6247,6947,6047,6547,3547,9547,4547,4507,

5507,5107,5407,5417,2417,7417,7717,7517,3517,3917,3947,

3907,3407,3467,3457,4457,4357,4337,4397,4597,4591,5591,

5791,9791,9091,1091,6091,6691,3691,7691,4691,4091,4391,

3391,3331,3371,3271,3221,3821,3881,3889,4889,1889,1289,

4289,4229,1229,7229,7219,4219,8219,8269,8209,3209,9209,

9239,2239,2269,2069,2969,2963,2063,2663,1663,4663,4363,

4373,3373,1373,1873,1823,1123,8123,8423,1423,4423,2423,

2473,6473,9473,9173,9133,9733,9743,9749,9349,9319,1319,

1399,5399,5393,5693,1693,8693,8093,1093,4093,4099,4079,

3079,3089,3989,3389,8389,2389,6389,6359,6353,8353,8053,

2053,6053,6043,7043,7013,1013,9013,9613,9623,3623,5623,

5923,9923,3923,3943,3643,3343,9343,6343,6143,6133,6833,

6803,6703,7703,7753,7757,7057,7457,7451,7411,2411,2441,

2141,2143,2843,5843,5813,5413,5443,5449,6449,6469,3469,

3169,3163,1163,1063,1033,1733,3733,4733,4133,4933,4937,

4957,4057,4657,4651,4451,4751,4051,4951,8951,7951,1951,

1051,5051,5011,5021,1021,1721,1741,7741,7841,6841,6871,

1871,9871,4871,4831,1831,8831,8731,2731,2531,5531,1531,

1031,1061,3061,3761,3361,6361,6661,9661,9461,9491,6491,

6991,6791,6781,6761,6961,6967,6977,6907,6007,9007,9907,

1907,1307,1303,5303,5333,5233,5237,5737,5717,5711,2711,

2791,2741,2749,5749,5743,5741,5641,5441,5431,5231,1231,

1237,1277,9277,9227,9221,9421,4421,4441,4481,7481,1481,

6481,6451,1451,1471,5471,5171,1171,1181,1381,1361,1321,

7321,7621,4621,2621,1621,1601,9601,9901,1901,7901,7001,

3001,3041,3011,3911,3931,4931,1931,9931,9631,3631,3637,

3037,6037,6337,6397,6997,6197,6199,9199,9109,1109,7109,

3109,3119,3019,3919,7919,7019,1019,1619,6619,6719,2719,

8719,8419,5419,5479,9479,9439,9839,9833,9883,9803,2803,

8803,3803,3863,3823,3853,3833,3533,9533,9539,2539,2039,

2939,5939,5639,5839,5039,5059,5659,5653,6653,6673,6073,

6079,6779,6709,1709,1759,1259,4259,4759,7759,7559,1559,

1579,1571,3571,3671,2671,2971,8971,8941,8741,8641,8681,

7681,7687,2687,2087,2887,2837,2437,5437,9437,9337,9137,

9127,7127,7177,7477,2477,5477,5077,5087,5987,5387,5381,

5351,2351,7351,7331,7333,7433,1433,3433,3413,3613,3313,

3319,3359,3259,3257,9257,6257,6857,2857,9857,9859,9851,

3851,2851,2551,9551,9521,8521,8501,8581,3581,6581,6521,

6421,6221,6211,4211,7211,7213,2213,2273,5273,8273,8573,

5573,5503,5563,6563,6569,6269,6869,6899,6599,6299,3299,

3499,3449,3049,1049,4049,4649,4643,7643,9643,9043,9049,

9059,9029,2029,6029,6089,2089,8089,8059,8069,8369,8669,

8629,8689,2689,9689,6689,5689,5189,5179,5779,8779,3779,

3709,3701,3301,1301,6301,6101,6701,5701,5101,5801,5807,

5857,5827,5867,5167,3167,8167,8867,8807,8887,8087,8387,

8377,8677,8647,8627,1627,1657,1667,1867,7867,7817,7877,

7577,7547,7537,7507,7907,7937,7237,7247,7243,2243,8243,

8443,8447,4447,1447,1487,7487,7187,1187,3187,3137,2137,

2131,6131,6151,6551,6553,1553,1453,1493,4493,4463,3463,

9463,9413,9403,9433,9431,8431,8231,8233,8293,8893,8863,

8563,8263,6263,6163,6173,6373,6379,6329,6529,6229,6829,

9829,9929,9949,7949,6949,6959,6659,3659,3559,3539,8539,

8599,8699,1699,7699,7499,1499,1489,7489,7789,1789,2789,

2729,2129,1129,4129,4139,4159,4157,9157,9187,9587,9887,

9817,9811,1811,1511,9511,3511,3541,7541,7561,7591,2591,

2521,2221,8221,8291,1291,1201,4201,4801,1801,2801,2861,

1861,4861,4561,4567,1567,1367,6367,6067,3067,9067,9767,

9787,1787,4787,4987,1987,1087,1097,1997,1597,8597,8527,

5527,5227,5297,5197,5897,2897,2297,2797,3797,3727,3767,

3769,3719,3739,9739,9769,9719,9419,9619,9629,9649,9679,

6679,4679,4673,4603,4903,4703,4783,4793,4799,4789,4729,

4723,1723,7723,7727,7027,7927,5927,2927,2917,2617,3617,

3607,3697,1697,9697,9397,9391,9311,2311,8311,6311,6011,

2011,8011,8081,2081,2281,2251,3251,3253,3203,6203,2203,

9203,9293,2293,2593,2693,2633,2833,2333,2339,4339,4349,

7349,7369,7309,5309,5209,5279,1279,1979,1949,1249,1549,

4549,2549,2579,2179,8179,8171,8191,3191,3491,3461,8461,

8467,2467,2767,2267,2237,2207,7207,7307,3307,3347,5347,

5147,8147,8747,8707,2707,2777,1777,1747,1847,3847,3877,

1877,4877,4177,4127,4327,1327,1427,6427,6827,6823,6323,

3323,9323,5323,5023,3023,3083,2083,2683,2383,2393,2399,

2309,2609,1609,8609,8009,1009,5009,5099,2099,2699,2999,

2909,2903,5903,5003,2003,2503,2543,1543,8543,8513,8713,

2713,2753,1753,8753,8783,1783,5783,5683,5483,1483,4483,

4583,1583,7583,3583,3593,3793,6793,7793,7393,7193,1193,

1103,9103,7103,7603,7607,1607,6607,6637,1637,4637,4639,

7639,7649,7549,7589,7529,7829,7129,7159,7459,1459,2459,

2659,2657,2677,9677,3677,3673,7673,7573,7523,1523,4523,

4513,4013,4813,4817,4517,4519,4019,4919,4999,1999,8999,

8929,8969,8963,8363,8663,8623,8923,8933,1933,7933,7963,

7993,1993,4993,4943,4973,9973,1973,1913,1613,1213,1223,

1283,9283,7283,7253,7853,7823,7883,7873,7879,1879,2879,

2819,8819,8849,5849,5879,5869,5861,5261,5281,9281,9241,

9341,9941,9041,9011,9001,4001,4007,4003,4073,4273,4271,

4261,4231,4241,4243,4283,4253,4153,1153,5153,5953,2953,

2153,2113,6113,5113,5119,5519,5569,5669,7669,1669,1069,

7069,7079,7039,1039,8039,8839,8837,8537,8237,8737,6737,

6733,6763,6863,6883,6983}
 

 

Q2:

Yes, I believe it is possible to find many different rows with the 

largest possible number of primes for any k. I also conjecture that there

exist cyclic ones with that property.

...

Here are also my largest rows for k=5 and k=6 for Q1:

(k=5, K=7243)

(k=6, K=58789)  

I am sending you 2 files with all the data for k=5 and k= 6.  Both are not the largest possible

 

***

Hürter wrote:

For K = 3 I found the following solution with K = 143:

 

419 719 709 509 599 499 479 179 149 449 409 809 839 239 233 733 739 439 433 443 463 163 193 173 373 383 983 683 643 743 773 673 677 277 257 557 457 157 757 787 797 997 397 307 607 907 947 937 337 347 349 389 379 359 353 953 653 613 617 647 547 587 577 571 541 521 421 431 331 131 137 197 199 139 109 107 127 227 727 827 887 487 467 167 967 367 317 311 313 113 103 101 401 461 761 751 701 601 641 631 661 691 491 991 191 151 251 271 211 811 821 881 181 281 241 941 911 971 977 877 857 859 659 619 919 929 829 229 223 293 283 883 823 853 863 263 269 769 569 563 593 523 503
 

 

***

Alessandro wrote:

Q1:

This puzzle quickly becomes quite lengthy. For k=3, the longest solution I’ve found until now is 128-long:

101, 103, 107, 109, 139, 131, 137, 127, 157, 151, 181, 191, 193, 197, 199, 149, 179, 173, 113, 163, 167, 367, 317, 311, 313, 353, 359, 349, 347, 337, 331, 431, 433, 439, 419, 449, 443, 463, 461, 467, 457, 487, 587, 547, 541, 521, 523, 563, 569, 599, 593, 293, 223, 227, 229, 239, 233, 263, 269, 769, 761, 751, 757, 727, 787, 797, 397, 997, 991, 911, 919, 929, 829, 821, 823, 827, 857, 853, 859, 839, 739, 733, 743, 773, 373, 379, 389, 383, 283, 281, 211, 241, 251, 257, 557, 577, 571, 271, 277, 877, 887, 881, 883, 983, 953, 653, 659, 619, 617, 677, 673, 683, 613, 643, 647, 947, 967, 937, 977, 971, 941, 641, 661, 631, 691, 491, 499, 479

out of a total of 143 primes. Let me point out that it isn’t definitive, there may be a bigger solution.

Q2:

Obviously I don't know, but I came up with a different way of looking at it. Since the digit change is a symmetric relation, then we can interpret the primes of k digits as nodes of a simple undirected graph, where the edges connect the primes that differ by only one digit. So the question is equivalent to find an hamiltonian path for this graph, i.e. if the graph is traceable. Unfortunately this problem is very unworkable, given that is NP and is an open problem even for the simplest graph classes. However, It is easy and quite inexpensive to find the adjacency matrix, node’s degree, Fiedler value, etc of this primes’ graph. As far as I know (and graph theory is my achilles heel), there are only some sufficient conditions, and the necessary condition of being connected. The case k=3 that I analyzed is unfortunately connected, with minimum degree equal to 3,  but does not satisfy any of the sufficient conditions, therefore I can say nothing a priori.

Let me point out an heuristic analysis. If the digit’s changing is interpreted as a series of random draws without replacement, then the average number of primes obtained (i.e. the mean node degree) and the relative variance tends to a constant as k (and so the number of nodes) becomes arbitrarily large, so the graph becomes less and less dense. Actually this means nothing (the cycle graph has everywhere degree equal to 2 and it’s even hamiltonian), but it can be said that it is less and less likely to be a traceable graph, namely to have longest possible sequence of this puzzle.

***

Claudio wrote:

k=3, K= 127, (Not maximal)

 

313, 113, 103, 101, 107, 109, 139, 131, 137, 127, 157, 151, 181, 191, 193, 163, 167, 197, 199, 149, 179, 173, 373, 353, 359, 349, 347, 307, 317, 311, 211, 241, 251, 257, 227, 223, 229, 239, 233, 263, 269, 569, 509, 409, 401, 421, 431, 331, 337, 367, 397, 797, 727, 757, 457, 467, 461,
463, 433, 439, 419, 449, 443, 643, 613, 617, 607, 601, 631, 641, 541, 521, 523, 503, 563, 593, 293, 283, 281, 271, 277, 577, 547, 557, 587, 487, 787, 887, 827, 821, 811, 881, 883, 383, 389, 379, 479, 499, 491, 691, 661, 761, 701, 709, 719, 619, 659, 653, 673, 677, 647, 947, 907, 937, 967, 977, 877, 857, 853, 823, 829, 809, 839, 739, 733, 743, 773
 

 

k=4, K= 726, (Not maximal)
 

 

7109, 1109, 1009, 1019, 1013, 1033, 1031, 1021, 1051, 1061, 1063, 1069, 1039, 1049, 1249, 1229, 1129, 1123, 1103, 1153, 1151, 1171, 1181, 1187, 1087, 1097, 1091, 1093, 1193, 1163, 1663, 1613, 1213, 1217, 1117, 8117, 8017, 2017, 2011, 2081, 2083, 2003, 2053, 2063, 2069, 2029, 2027, 2087, 2089, 2039, 2099, 2399, 1399, 1319, 1619, 1609, 1409, 1429, 1423, 1223, 1283, 1289, 1259, 1279, 1277, 1237, 1231, 1201, 1291, 1297, 1597, 1567, 1367, 1307, 1301, 1303, 1373, 1873, 1823, 1523, 1543, 1549, 1559, 1459, 1439, 1433, 1453, 1451, 1471, 1481, 1381, 1321, 1327, 1427, 1447, 1487, 1483, 1489, 1499, 1493, 1693, 1697, 1607, 1601, 1621, 1627, 1637, 1657, 1667, 1669, 1699, 1999, 1949, 1979, 1579, 1571, 1511, 1531, 1831,
1801, 1811, 1861, 1361, 3361, 3061, 3001, 3011, 3019, 3049, 3041, 3541, 3511, 3517, 3217, 3257, 3251, 2251, 2221, 2281, 2287, 2207, 2203, 2213, 2113, 2111, 2131, 2137, 2237, 2239, 2269, 2267, 2297, 2293, 2243, 2143, 2141, 2161, 2861, 2801, 2803, 2503, 2543, 2549, 2539, 2339, 2309, 2389, 2381, 2311, 2341, 2347, 2357, 2351, 2371, 2377, 2477, 2417, 2411, 2441, 2447, 2437, 2467, 2767, 2707, 2777, 1777, 1747, 1741, 1721, 1723, 1733, 1753, 1553, 1583, 1783, 1787, 1789, 1709, 1759, 4759, 4159, 4129, 2129, 2179, 2579, 2879, 1879, 1871, 1877, 1847, 1867, 5867, 5167, 3167, 3067, 3037, 3137, 3187, 3181, 3121, 3191, 3391, 3301, 3307, 3347, 3343, 3313, 3319, 3119, 3109, 3169, 3163, 3463, 3413, 3433, 3533, 3539, 3529, 3229, 3209, 3203, 3253, 3259, 3299, 3499, 3449, 3469, 3461, 3467, 3407, 3457, 3557, 2557, 2551, 2521, 2531, 2591, 2593, 2393, 2333, 2383, 2683,
2633, 2663, 2693, 2699, 2609, 2659, 2459, 7459, 7159, 7129, 7121, 6121, 6101, 5101, 5107, 5147, 5197, 5297, 4297, 4217, 4211, 4111, 8111, 8011, 5011, 5021, 4021, 4001, 4003, 4007, 4027, 4057, 4051, 4091, 4093, 4013, 4019, 4049, 4079, 3079, 3089, 3083, 3023, 3323, 3329, 3359, 3389, 3889, 1889, 4889, 4289, 4219, 4229, 4259, 4253, 4153, 2153, 2753, 2713, 2711, 2719, 2729, 2749, 2741, 2731, 2791, 2797, 2897, 2837, 2833, 2843, 5843, 5443, 5413, 5113, 5119, 5179, 5171, 5471, 5431, 5231, 4231, 4201, 4241, 4243, 4273, 2273, 2473, 2423, 4423, 4421, 4441, 4447, 4457, 4157, 4127, 4177, 4877, 3877, 3677, 2677, 2617, 2647, 2657, 2687, 2689, 2789, 4789, 4729, 4721, 4621, 2621, 2671, 2971, 6971, 6271, 3271, 3221, 3821, 3823, 3623, 3613, 3617, 3607, 3637, 3631, 3331, 3371, 3373, 3673, 3643, 3943, 3923, 3929, 3919, 3719, 3709, 3701, 3761, 3767, 3727, 3527, 3547,
3847, 3947, 3907, 1907, 1901, 1931, 1933, 1913, 1973, 1993, 1997, 1987, 4987, 4787, 4783, 4283, 4483, 4463, 4363, 4373, 4073, 4673, 4603, 4643, 4649, 4349, 4339, 4139, 4133, 4733, 3733, 3739, 3769, 3779, 5779, 5279, 5209, 5009, 5003, 5023, 5323, 5303, 5309, 5399, 5099, 4099, 4799, 4793, 3793, 3593, 3583, 3581, 3571, 3671, 3691, 3491, 6491, 6091, 6011, 6211, 6217, 6247, 6047, 6007, 6037, 6067, 6367, 6317, 6311, 6301, 6361, 6661, 6691, 4691, 4391, 4397, 4327, 4337, 4357, 4657, 4637, 4639, 4679, 6679, 6079, 6029, 6089, 6389, 6329, 6229, 6221, 6421, 6427, 6827, 5827, 5227, 5237, 5233, 5273, 5573, 5503, 5501, 5507, 4507, 4517, 4513, 4519, 4549, 4547, 4567, 4561, 4261, 4271, 4871, 4801, 4831, 4861, 5861, 5261, 5281, 5081, 5051, 5059, 5039, 5639, 5659, 3659, 3559, 7559, 7529, 6529, 6521, 5521, 5527, 5557, 5657, 5647, 5347, 5387, 5087, 5077, 5477, 5407,
5417, 5419, 5449, 5441, 5641, 5651, 4651, 4451, 4481, 6481, 6451, 6151, 6131, 6133, 6113, 6143, 6043, 6053, 6073, 6173, 6163, 6263, 6203, 6703,, 5333, 7333, 7331, 7321, 7351, 5351, 5381, 5581, 5531, 5591, 4591, 4597, 8597, 8297, 7297, 7207, 7237, 7247, 7547, 6547, 6947, 6907, 6607, 6637, 6337, 6397, 6197, 6199, 6299, 6269, 6469, 6449, 6949, 6959, 6359, 6353, 6323, 6343, 6373, 6379, 6779, 6709, 6701, 5701, 5711, 5717, 5737, 5437, 9437, 9137, 9127, 9157, 9151, 7151, 7451, 7481, 7489, 7499, 7699, 7639, 7649, 7349, 7309, 7307, 7507, 7517, 7537, 7937, 4937, 4931, 3931, 3911, 3917, 2917, 2927, 2957, 2857, 2851, 3851, 3853, 3803, 3833, 3863, 6863, 6563, 5563, 5569, 5519

***

Rebert wrote:

Q1. My best results are the followings :

The k-digit prime sequence begins with p1 and ends with pK.

 

k        K         p1        pK    % of k-digit primes chained

1        4           2           7 100

2      21         97         83 100

3   127        313       773  89

4   726      7189     5318  68

5 2849    86287   32621  34

6 4895  233591 113837    7

 

I sent my sequences as an attached file. 

 

Q2. I believe that the probability of this hypothesis become near of zero with great values of k-digits primes. 

 

Difficult to answer to this question, but F

 

For k = 1, 2, 3, ... 6 respectively the chained primes represent 100%, 100%,  89%,  68% , 34% ,  7% of the k_digits primes.

***

Adam wrote:

Starting with a given prime, I switch all the digits one by one and then filter to get a list of next possible primes.  I randomly pick one, and loop back to all possibles.  In this fashion, I get list lengths hovering around 1/3 to a 1/2 of the total count of primes with the given number of digits.  I think the long list is going to take up too much space and is not really useful but I will share with interested parties.  I obtained a list of length 18645 for 6 digits primes starting at 910447, 610447, 617447, 617467 and ending with 917689, 917659, 987659, 983659 as well as a list of length 4168 of five digit primes starting with 11351,11311,11317,21317.  These lists pop up pretty quickly, under an hour, so there are probably many such lists.

 

To be methodical (the 2nd question, is a complete list of all primes possible), you could set up a graph where the vertices are all the primes and edges if two primes differ by a single digit.  Then you are looking for a Hamilton path---labor intensive, both data-wise and algorithmically.  The theorem (Ore?) often quoted on the web is if there are n vertices, each with degree n/2, then there is a Hamilton path but we are nowhere near the correct degree.

 

I updated the game plan to try 100 different random digit switches for a given first prime and I am up to 827 of the 1061 four digit primes.  I also went through 8 digit primes (I know that wasn't part of the puzzle) and got to a string of just under 2 million but the program doesn't have enough memory to type it out.

 

***

Emmanuel wrote:

For K = 3 I found a sequence of 141 primes :
773, 743, 733, 739, 839, 859, 829, 929, 229, 239, 269, 769, 569, 509, 709, 809, 409, 439, 449, 479, 499, 419, 619, 719, 919, 911, 971, 941, 991, 997, 977, 967, 937, 907, 947, 647, 617, 607, 677, 877, 857, 827, 823, 853, 863, 883, 887, 787, 587, 487, 467, 457, 557, 547, 577, 277, 257, 227, 727, 797, 397, 347, 337, 317, 307, 367, 167, 137, 127, 197, 199, 599, 593, 503, 523, 563, 463, 433, 443, 643, 653, 683, 613, 673, 373, 353, 313, 383, 983, 283, 263, 233, 223, 293, 193, 173, 163, 113, 103, 107, 157, 757, 751, 761, 701, 601, 631, 691, 661, 641, 541, 571, 521, 821, 811, 881, 281, 271, 251, 241, 211, 311, 331, 431, 461, 421, 401, 491, 191, 181, 151, 131, 101, 109, 139, 149, 179, 379, 349, 359, 389
But I cannot prove it's maximal.
 I also found a sequence of 139 primes, the first and the last differing from one digit :
{859, 839, 829, 929, 229, 239, 269, 769, 569, 509, 709, 809, 409, 439, 449, 479, 499, 419, 619, 719, 919, 911, 971, 941, 991, 997, 977, 967, 937, 907, 947, 647, 617, 607, 677, 877, 857, 827, 823, 853, 863, 883, 887, 787, 587, 487, 467, 457, 557, 547, 577, 277, 257, 227, 727, 797, 397, 347, 337, 317, 307, 367, 167, 137, 127, 197, 199, 599, 593, 503, 523, 563, 463, 433, 443, 743, 643, 653, 683, 613, 673, 773, 373, 353, 313, 383, 983, 283, 263, 233, 223, 293, 193, 173, 163, 113, 103, 107, 157, 757, 751, 761, 701, 601, 631, 691, 661, 641, 541, 571, 521, 821, 811, 881, 281, 271, 251, 241, 211, 311, 331, 431, 461, 421, 401, 491, 191, 181, 151, 131, 101, 109, 139, 149, 179, 379, 349, 389, 359}}:.
But I cannot prove that this is maximal.

For K = 6 we know that there are weakly primes : 294001,505447,584141,604171,929573,971767.  Changing one digit turns them into a composite number.
Thus, these primes cannot appear in a solution.  The maximum length hence will be <= 68906 = A006879(6) = the number of primes with  6  digits.
 

I think the number of weakly primes with  K  digits increases with  K, so the maximum lengths will differ from  A006879.

 

***