Problems & Puzzles: Puzzles

Puzzle 963. Minimal quantity of Prime Arithmetic Progressions to... Dmitry Kamenetsky poses the following nice puzzle: Observe that the first 10 odd primes can be covered with a minimal of three arithmetic progressions of primes:   For X=10, K=3: {(3,17,31); (5,11,17,23,29); (7,13,19)} What is the smallest number of arithmetic progressions of primes, K, needed to cover the first X odd primes? Do this for: Q1. X=100 Q2. X=1000.

---

Contributions came from Dmitry Kamenetsky, Emmanuel Vantieghem

***

Dmitry wrote on July 29-30, 2019:

I was able to find 26 progressions with 3+ terms that cover the first 100 primes.

 

(3,181,359), (5,11,17,23,29), (7,37,67,97,127,157), (7,109,211,313), (11,41,71,101,131), (13,103,193,283,373,463), (19,79,139,199), (29,149,269,389,509), (31,97,163,229), (43,271,499), (47,59,71,83), (53,113,173,233,293,353), (61,151,241,331,421), (73,223,373,523), (89,269,449), (107,137,167,197,227,257), (179,281,383), (191,317,443), (227,239,251,263), (277,307,337,367,397), (277,367,457,547), (311,347,383,419), (349,379,409,439), (379,433,487,541), (401,431,461,491,521), (467,479,491,503)

...

I can cover 1000 primes with 248 progressions with 3 or more terms.

(3,3623,7243), (5,1571,3137,4703,6269), (7,157,307,457,607,757,907), 
(11,71,131,191,251,311), (13,103,193,283,373,463), (17,2999,5981), 
(19,439,859,1279,1699), (23,2411,4799,7187), (29,149,269,389,509), 
(31,1201,2371,3541), (37,1327,2617,3907,5197), (41,47,53,59), 
(43,271,499,727), (43,733,1423,2113,2803), (61,67,73,79), 
(61,151,241,331,421), (83,383,683,983,1283,1583), (89,2693,5297,7901), 
(97,877,1657,2437,3217), (101,641,1181,1721), (107,227,347,467,587), 
(109,1483,2857,4231), (113,281,449,617), (127,1237,2347,3457,4567), 
(137,353,569), (139,853,1567,2281), (149,2399,4649,6899), 
(163,1663,3163,4663,6163), (167,2087,4007,5927), (173,3371,6569), 
(179,809,1439,2069,2699,3329), (181,1741,3301,4861,6421), 
(193,613,1033,1453,1873,2293,2713), (197,1877,3557,5237,6917), 
(199,409,619,829,1039,1249,1459,1669,1879,2089), (211,337,463), 
(223,3187,6151), (229,2053,3877,5701), (233,2753,5273,7793), 
(239,359,479,599,719,839), (257,1733,3209), (263,563,863,1163), 
(277,883,1489), (293,1511,2729,3947), (313,541,769,997), 
(317,1607,2897), (349,709,1069,1429,1789), (359,1523,2687,3851), 
(367,1609,2851,4093), (379,1549,2719,3889,5059,6229), 
(397,577,757,937,1117,1297), (401,1061,1721,2381,3041,3701), 
(419,719,1019,1319,1619), (431,4079,7727), (433,2143,3853,5563), 
(443,4073,7703), (461,1601,2741,3881,5021), (487,1597,2707), 
(491,821,1151,1481,1811,2141), (503,1913,3323,4733,6143), 
(509,653,797,941), (521,977,1433,1889), (523,1327,2131), (547,643,739), 
(557,827,1097,1367,1637,1907), (571,631,691,751,811), 
(593,1451,2309,3167), (601,2377,4153), (647,1217,1787,2357,2927), 
(659,2339,4019), (661,2971,5281,7591), (673,1213,1753,2293,2833,3373), 
(677,2447,4217,5987,7757), (701,1427,2153,2879), 
(743,2273,3803,5333,6863), (757,2689,4621,6553), (761,857,953,1049), 
(773,1583,2393,3203,4013), (787,2029,3271,4513), 
(823,1063,1303,1543,1783), (881,4229,7577), (887,929,971,1013), 
(911,3359,5807), (919,2473,4027,5581), (947,3617,6287), (967,3967,6967), 
(991,2887,4783,6679), (1009,1699,2389,3079,3769), 
(1013,1103,1193,1283,1373), (1021,1171,1321,1471,1621), 
(1031,2111,3191,4271,5351), (1051,1777,2503,3229), 
(1087,2467,3847,5227,6607), (1091,2591,4091,5591), 
(1093,3253,5413,7573), (1109,1259,1409,1559,1709), (1109,4463,7817), 
(1123,2383,3643,4903,6163), (1129,4441,7753), (1153,2161,3169,4177), 
(1187,2099,3011,3923), (1223,2081,2939,3797), (1229,3083,4937,6791), 
(1231,1951,2671,3391,4111,4831), (1277,3347,5417,7487), 
(1289,1493,1697,1901), (1291,1747,2203,2659), 
(1301,2441,3581,4721,5861,7001), (1307,1487,1667,1847,2027,2207), 
(1361,3167,4973,6779), (1381,1831,2281,2731,3181,3631), 
(1399,2749,4099,5449), (1427,2777,4127,5477,6827), (1447,4657,7867), 
(1459,1723,1987,2251), (1471,2137,2803,3469), (1499,1871,2243), 
(1531,3061,4591,6121), (1553,2963,4373,5783,7193), (1579,4003,6427), 
(1613,4421,7229), (1627,3727,5827,7927), (1627,4519,7411), 
(1693,2683,3673,4663,5653), (1753,2593,3433,4273,5113,5953,6793), 
(1759,3463,5167,6871), (1801,1867,1933,1999), (1823,4703,7583), 
(1861,3331,4801,6271,7741), (1931,2417,2903,3389), (1949,1973,1997), 
(1979,2819,3659), (1993,2803,3613,4423,5233,6043), 
(2003,2213,2423,2633,2843), (2011,3511,5011), (2017,3019,4021,5023), 
(2039,3089,4139,5189), (2063,3491,4919), (2083,2311,2539,2767), 
(2129,2459,2789,3119,3449,3779), (2179,3049,3919,4789,5659,6529), 
(2213,3761,5309,6857), (2221,2791,3361,3931), (2237,4943,7649), 
(2239,3943,5647,7351), (2267,3989,5711,7433), (2269,3739,5209,6679), 
(2287,3307,4327,5347,6367), (2297,2477,2657,2837), 
(2333,3413,4493,5573,6653), (2341,2647,2953,3259), 
(2351,2441,2531,2621,2711,2801), (2437,2557,2677,2797,2917,3037), 
(2441,3461,4481,5501,6521,7541), (2521,4201,5881,7561), 
(2543,4211,5879,7547), (2549,2579,2609), (2551,3121,3691,4261,4831), 
(2663,3221,3779,4337), (2797,4159,5521,6883), (2833,5077,7321), 
(2861,2909,2957), (2969,3449,3929,4409,4889), (3001,4561,6121,7681), 
(3023,4691,6359), (3067,4297,5527), (3109,3313,3517), 
(3251,4241,5231,6221,7211), (3257,4679,6101,7523), 
(3299,3533,3767,4001), (3319,5503,7687), (3343,3697,4051), 
(3407,4289,5171,6053), (3413,3833,4253,4673), (3467,4259,5051,5843), 
(3499,3709,3919,4129,4339,4549,4759,4969,5179), 
(3527,4457,5387,6317,7247), (3529,4219,4909), (3539,4523,5507,6491), 
(3547,3559,3571,3583), (3593,3821,4049), 
(3607,4057,4507,4957,5407,5857), (3637,4999,6361,7723), 
(3671,4967,6263,7559), (3677,3917,4157,4397,4637,4877), 
(3719,5009,6299,7589), (3733,4363,4993,5623), (3793,4933,6073,7213), 
(3823,4951,6079,7207), (3851,4751,5651,6551,7451), (3863,4451,5039), 
(3911,5897,7883), (4133,5261,6389,7517), (4243,4363,4483,4603,4723), 
(4283,4793,5303,5813,6323,6833), (4349,5003,5657,6311), 
(4349,5099,5849,6599,7349), (4357,4729,5101), (4391,4517,4643), 
(4447,5119,5791), (4547,4817,5087), (4583,5393,6203,7013,7823), 
(4597,5689,6781,7873), (4639,5323,6007,6691), (4651,5431,6211,6991), 
(4787,5147,5507,5867), (4813,5743,6673,7603), 
(4871,5441,6011,6581,7151), (4931,5081,5231,5381,5531), 
(4987,5419,5851), (5107,6373,7639), (5153,5483,5813,6143,6473,6803), 
(5279,5399,5519,5639), (5437,5737,6037,6337,6637), 
(5443,5821,6199,6577), (5471,6257,7043,7829), 
(5479,5569,5659,5749,5839), (5557,6277,6997,7717), 
(5641,6301,6961,7621), (5669,5693,5717,5741), (5683,6451,7219), 
(5779,6199,6619,7039,7459,7879), (5801,6737,7673), 
(5869,6133,6397,6661), (5903,6911,7919), (5923,6247,6571), 
(5939,6329,6719,7109,7499), (6029,6113,6197), (6047,6089,6131,6173), 
(6067,6547,7027,7507), (6091,6217,6343,6469), (6353,7103,7853), 
(6379,6709,7039,7369,7699), (6449,6659,6869,7079), 
(6481,6907,7333,7759), (6563,7127,7691), 
(6673,6703,6733,6763,6793,6823), (6689,7283,7877), 
(6701,6977,7253,7529), (6761,7121,7481,7841), 
(6829,7069,7309,7549,7789), (6841,7159,7477), (6947,6959,6971,6983), 
(6949,7129,7309,7489,7669), (7019,7331,7643), 
(7057,7177,7297,7417,7537), (7237,7393,7549), (7307,7457,7607,7757,7907)

***

Emmanuel wrote on July 30, 20019

Q1 :

I got a set of 36 arithmetic progressions that cover the first 100 odd primes :

{{3, 263, 523}, {499, 523, 547}, {19, 193, 367, 541}, {31, 157, 283, 409},

 {59, 83, 107, 131}, {67, 109, 151, 193}, {73, 223, 373, 523}, {79, 193, 307, 421}, {127, 139, 151, 163}, {127, 229, 331, 433}, {157, 199, 241, 283}, {239, 293, 347, 401}, {277, 367, 457, 547}, {281, 317, 353, 389}, {313, 331, 349, 367}, {349, 379, 409, 439}, {379, 433, 487, 541}, {467, 479, 491, 503}, {5, 11, 17, 23, 29}, {5, 47, 89, 131, 173}, {5, 131, 257, 383, 509}, {11, 41, 71, 101, 131}, {29, 149, 269, 389, 509}, {43, 103, 163, 223, 283}, {61, 151, 241, 331, 421}, {83, 173, 263, 353, 443}, {89, 179, 269, 359, 449}, {151, 181, 211, 241, 271}, {277, 307, 337, 367, 397}, {401, 431, 461, 491, 521}, {7, 37, 67, 97, 127, 157}, {11, 71, 131, 191, 251, 311}, {13, 103, 193, 283, 373, 463}, {53, 113, 173, 233, 293, 353}, {107, 137, 167, 197, 227, 257}, {359, 389, 419, 449, 479, 509}}
 

It is minimal in the sense that no arithmetic progression can be removed from the set.

 

Q2 :  I found a set of 310 arithmetic progressions that cover the first 1000 odd primes [sent in an annex].

***

On August 9, 2019 Gennady Gusev wrote:

I was able to improve previous solution. I covered  1000 primes with 235 progressions:

(3499, 3709, 3919, 4129, 4339, 4549, 4759, 4969, 5179), (199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089), (1637, 2267, 2897, 3527, 4157, 4787, 5417, 6047), (881, 1091, 1301, 1511, 1721, 1931, 2141, 2351), (4259, 4679, 5099, 5519, 5939, 6359, 6779), (193, 613, 1033, 1453, 1873, 2293, 2713), (1619, 2039, 2459, 2879, 3299, 3719, 4139), (179, 389, 599, 809, 1019, 1229, 1439), (47, 257, 467, 677, 887, 1097, 1307), (1753, 2593, 3433, 4273, 5113, 5953, 6793), (53, 1103, 2153, 3203, 4253, 5303, 6353), (7, 157, 307, 457, 607, 757, 907), (1061, 1901, 2741, 3581, 4421, 5261, 6101), (379, 1549, 2719, 3889, 5059, 6229), (2957, 3947, 4937, 5927, 6917, 7907), (3607, 4057, 4507, 4957, 5407, 5857), (1993, 2803, 3613, 4423, 5233, 6043), (5153, 5483, 5813, 6143, 6473, 6803), (83, 383, 683, 983, 1283, 1583), (701, 1871, 3041, 4211, 5381, 6551), (1289, 1709, 2129, 2549, 2969, 3389), (2441, 3461, 4481, 5501, 6521, 7541), (739, 1999, 3259, 4519, 5779, 7039), (2833, 3253, 3673, 4093, 4513, 4933), (2437, 2557, 2677, 2797, 2917, 3037), (13, 223, 433, 643, 853, 1063), (1201, 1471, 1741, 2011, 2281, 2551), (1013, 1193, 1373, 1553, 1733, 1913), (937, 2287, 3637, 4987, 6337, 7687), (839, 1889, 2939, 3989, 5039, 6089), (1051, 2311, 3571, 4831, 6091, 7351), (2467, 3457, 4447, 5437, 6427, 7417), (2953, 3163, 3373, 3583, 3793, 4003), (1523, 2213, 2903, 3593, 4283, 4973), (5051, 5531, 6011, 6491, 6971, 7451), (4021, 4441, 4861, 5281, 5701, 6121), (2753, 3413, 4073, 4733, 5393, 6053), (2207, 2447, 2687, 2927, 3167, 3407), (5443, 5503, 5563, 5623, 5683, 5743), (4591, 5011, 5431, 5851, 6271, 6691), (367, 1567, 2767, 3967, 5167, 6367), (811, 1321, 1831, 2341, 2851, 3361), (11, 71, 131, 191, 251, 311), (7457, 7487, 7517, 7547, 7577, 7607), (541, 571, 601, 631, 661, 691), (1423, 2053, 2683, 3313, 3943), (43, 463, 883, 1303, 1723, 2143), (4243, 4363, 4483, 4603, 4723), (2243, 2393, 2543, 2693, 2843), (2063, 3323, 4583, 5843, 7103), (1951, 3001, 4051, 5101, 6151), (127, 457, 787, 1117, 1447, 1777), (37, 1327, 2617, 3907, 5197), (401, 431, 461, 491, 521), (5479, 5569, 5659, 5749, 5839), (509, 1979, 3449, 4919, 6389), (229, 619, 1009, 1399, 1789, 2179), (5021, 5231, 5441, 5651, 5861), (1877, 3347, 4817, 6287, 7757), (97, 1237, 2377, 3517, 4657), (6323, 6563, 6803, 7043, 7283, 7523), (6829, 7069, 7309, 7549, 7789), (5077, 5737, 6397, 7057, 7717), (1427, 2777, 4127, 5477, 6827), (1123, 2383, 3643, 4903, 6163), (19, 439, 859, 1279, 1699), (1493, 2663, 3833, 5003, 6173), (1249, 2239, 3229, 4219, 5209, 6199), (2251, 2521, 2791, 3061, 3331), (3727, 3877, 4027, 4177, 4327), (2237, 2297, 2357, 2417, 2477), (743, 2273, 3803, 5333, 6863), (6673, 6703, 6733, 6763, 6793, 6823), (1031, 2111, 3191, 4271, 5351), (149, 599, 1049, 1499, 1949, 2399), (1223, 1823, 2423, 3023, 3623), (5309, 5879, 6449, 7019, 7589), (3677, 3917, 4157, 4397, 4637, 4877), (5849, 6269, 6689, 7109, 7529), (2161, 2671, 3181, 3691, 4201), (151, 181, 211, 241, 271), (29, 719, 1409, 2099, 2789), (503, 593, 683, 773, 863, 953), (2381, 2591, 2801, 3011, 3221), (6679, 6949, 7219, 7489, 7759), (499, 1129, 1759, 2389, 3019), (2699, 2909, 3119, 3329, 3539), (1627, 1987, 2347, 2707, 3067), (1231, 2371, 3511, 4651, 5791), (5, 1433, 2861, 4289, 5717), (73, 223, 373, 523, 673, 823), (1571, 2411, 3251, 4091, 4931), (227, 587, 947, 1307, 1667, 2027), (1747, 2647, 3547, 4447, 5347, 6247), (2269, 2689, 3109, 3529), (53, 113, 173, 233, 293, 353), (3779, 4409, 5039, 5669, 6299), (1291, 3121, 4951, 6781), (6761, 7121, 7481, 7841), (6577, 7027, 7477, 7927), (47, 977, 1907, 2837, 3767), (2069, 3359, 4649, 5939, 7229), (1429, 3079, 4729, 6379), (359, 389, 419, 449, 479, 509), (3371, 4007, 4643, 5279), (4789, 5413, 6037, 6661), (3761, 4001, 4241, 4481, 4721), (89, 443, 797, 1151), (587, 887, 1187, 1487, 1787, 2087), (317, 1367, 2417, 3467, 4517), (3769, 4663, 5557, 6451), (2729, 4013, 5297, 6581), (5573, 6113, 6653, 7193), (4133, 5081, 6029, 6977), (2221, 3187, 4153, 5119), (1783, 3391, 4999, 6607), (5987, 6599, 7211, 7823), (7127, 7187, 7247, 7307), (2029, 2539, 3049, 3559), (67, 577, 1087, 1597), (7829, 7853, 7877, 7901), (487, 1609, 2731, 3853), (101, 1361, 2621, 3881), (4127, 4547, 4967, 5387, 5807), (4813, 5641, 6469, 7297), (3541, 4597, 5653, 6709), (751, 2887, 5023, 7159), (3217, 3739, 4261, 4783), (109, 1483, 2857, 4231), (4703, 5711, 6719, 7727), (2633, 3821, 5009, 6197), (6301, 6361, 6421, 6481), (653, 1481, 2309, 3137), (5867, 6329, 6791, 7253), (3671, 3797, 3923, 4049), (4111, 5227, 6343, 7459), (2137, 3469, 4801, 6133), (827, 1997, 3167, 4337, 5507), (1663, 1933, 2203, 2473), (1381, 2971, 4561, 6151, 7741), (5647, 6277, 6907, 7537), (547, 769, 991, 1213), (5881, 6547, 7213, 7879), (191, 821, 1451, 2081, 2711), (569, 1613, 2657, 3701), (563, 941, 1319, 1697), (3659, 4373, 5087, 5801), (1607, 2999, 4391, 5783), (1579, 3343, 5107, 6871), (919, 3169, 5419, 7669), (61, 397, 733, 1069), (163, 2131, 4099, 6067), (5527, 5869, 6211, 6553), (107, 137, 167, 197, 227, 257), (1163, 2843, 4523, 6203, 7883), (6659, 7079, 7499, 7919), (6529, 6883, 7237, 7591), (3257, 4457, 5657, 6857), (2017, 3319, 4621, 5923), (7411, 7507, 7603, 7699), (3089, 4673, 6257, 7841), (7177, 7369, 7561, 7753), (1621, 3307, 4993, 6679), (4567, 5323, 6079), (5189, 6311, 7433), (313, 2083, 3853, 5623, 7393), (347, 659, 971, 1283), (641, 911, 1181, 1451, 1721), (1021, 3931, 6841), (5147, 6029, 6911, 7793), (3209, 3851, 4493), (31, 67, 103, 139), (277, 349, 421), (1217, 3557, 5897), (3863, 4751, 5639), (269, 2531, 4793), (857, 3929, 7001), (283, 727, 1171), (4943, 5171, 5399), (1693, 3301, 4909), (1109, 4463, 7817), (3, 3847, 7691), (6569, 6701, 6833), (1153, 1321, 1489, 1657), (1093, 4357, 7621), (1867, 2749, 3631, 4513), (7643, 7673, 7703), (2003, 4451, 6899), (3491, 5237, 6983), (5, 23, 41, 59), (2659, 4639, 6619), (2099, 2339, 2579, 2819), (337, 3733, 7129), (7013, 7331, 7649), (647, 2333, 4019), (1709, 2963, 4217, 5471), (5021, 5261, 5501, 5741, 5981, 6221), (7639, 7681, 7723), (929, 2909, 4889, 6869), (593, 1601, 2609, 3617), (5437, 5827, 6217, 6607, 6997), (239, 3911, 7583), (709, 2503, 4297, 6091), (997, 4159, 7321), (263, 3083, 5903), (331, 1801, 3271), (4229, 5273, 6317), (1543, 2113, 2683, 3253, 3823), (1811, 3251, 4691, 6131), (281, 617, 953, 1289), (7573, 7723, 7873), (5521, 5581, 5641, 5701), (1559, 3533, 5507, 7481), (6151, 6571, 6991, 7411), (5693, 6263, 6833), (6373, 6871, 7369, 7867), (4079, 5519, 6959), (4871, 5441, 6011, 6581, 7151), (1297, 1579, 1861, 2143), (433, 3697, 6961), (5413, 5821, 6229, 6637), (79, 3643, 7207), (503, 761, 1019, 1277), (1531, 3769, 6007), (1847, 3323, 4799), (4349, 5099, 5849, 6599, 7349), (877, 907, 937, 967, 997), (1237, 3463, 5689), (17, 557, 1097, 1637), (1259, 1973, 2687), (4813, 5443, 6073, 6703, 7333), (6947, 7253, 7559), (5591, 6737, 7883), (3931, 5449, 6967), (3919, 5581, 7243)
 

***

 

---