Robinson Primes and the Sierpinski Problem

All primes must of necessity be of the form k.2n +1 for some odd k and some value of n. However, in view of the requirement for factors of Fermat Numbers, it is of interest to locate particular instances where either k is small and n is pushed as far as possible, or where n is small and k is pushed as far as possible. Viewed in this way, they are known as Robinson primes.

The following is a list of all values of n £ 4000 for each odd k < 100 such that k.2n + 1 is a prime. The number of such n for each k is also given.

 k p n 1 5 1, 2, 4, 8, 16 (Fermat Primes) 3 24 1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912 5 13 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313 7 21 2, 4, 6, 14, 20, 26, 50, 52, 92, 120, 174, 180, 190, 290, 320, 390, 432, 616, 830, 1804, 2256 9 31 1, 2, 3, 6, 7, 11, 14, 17, 33, 42, 43, 63, 65, 67, 81, 134, 162, 206, 211, 366, 663, 782, 1305, 1411, 1494, 2297, 2826, 3230, 3354, 3417, 3690 11 13 1, 3, 5, 7, 19, 21, 43, 81, 125, 127, 209, 211, 3225 13 10 2, 8, 10, 20, 28, 82, 188, 308, 316, 1000 15 26 1, 2, 4, 9, 10, 12, 27, 37, 38, 44, 48, 78, 112, 168, 229, 297, 339, 517, 522, 654, 900, 1518, 2808, 2875, 3128, 3888 17 12 3, 15, 27, 51, 147, 243, 267, 347, 471, 747, 2163, 3087 19 6 6, 10, 46, 366, 1246, 2038 21 23 1, 4, 5, 7, 9, 12, 16, 17, 41, 124, 128, 129, 187, 209, 276, 313, 397, 899, 1532, 1613, 1969, 2245, 2733 23 14 1, 9, 13, 29, 41, 49, 69, 73, 341, 381, 389, 649, 1961, 3929 25 24 2, 4, 6, 10, 20, 22, 52, 64, 78, 184, 232, 268, 340, 448, 554, 664, 740, 748, 1280, 1328, 1640, 3314, 3904, 3938 27 26 2, 4, 7, 16, 19, 20, 22, 26, 40, 44, 46, 47, 50, 56, 59, 64, 92, 175, 215, 275, 407, 455, 1076, 1090, 3080, 3322 29 20 1, 3, 5, 11, 27, 43, 57, 75, 77, 93, 103, 143, 185, 231, 245, 391, 1053, 1175, 2027, 3627 31 8 8, 60, 68, 140, 216, 416, 1808, 1944 33 21 1, 6, 13, 18, 21, 22, 25, 28, 66, 93, 118, 289, 412, 453, 525, 726, 828, 1420, 1630, 3076, 3118 35 20 1, 3, 7, 9, 13, 15, 31, 45, 47, 49, 55, 147, 245, 327, 355, 663, 1423, 1443, 2493, 3627 37 26 2, 4, 8, 10, 12, 16, 22, 26, 68, 82, 84, 106, 110, 166, 236, 254, 286, 290, 712, 1240, 1706, 1804, 1904, 2240, 2632, 3104 39 30 1, 2, 3, 5, 7, 10, 11, 13, 14, 18, 21, 22, 31, 42, 67, 70, 71, 73, 251, 370, 375, 389, 407,518, 818, 865, 1057, 1602, 2211, 3049 41 7 1, 11, 19, 215, 289, 379, 1991 43 17 2, 6, 12, 18, 26, 32, 94, 98, 104, 144, 158, 252, 778, 1076, 2974, 3022, 3528 45 16 2, 9, 12, 14, 23, 24, 29, 60, 189, 200, 333, 372, 443, 464, 801, 1374 47 2 583, 1483 49 12 2, 6, 10, 30, 42, 54, 66, 118, 390, 594, 1202, 2334 51 28 1, 3, 7, 9, 13, 17, 25, 43, 53, 83, 89, 92, 119, 175, 187, 257, 263, 267, 321, 333, 695, 825, 1485, 1917, 2660, 2967, 3447, 3659 53 14 1, 5, 17, 21, 61, 85, 93, 105, 133, 485, 857, 1665, 2133, 2765 55 15 4, 8, 16, 22, 32, 94, 220, 244, 262, 286, 344, 356, 392, 1996, 2744 57 22 2, 3, 7, 8, 10, 16, 18, 19, 40, 48, 55, 90, 96, 98, 190, 398, 456, 502, 719, 1312, 1399, 1828 59 7 5, 11, 27, 35, 291, 1085, 2685 61 6 4, 12, 48, 88, 168, 3328 63 37 1, 4, 5, 9, 10, 14, 17, 18, 21, 25, 37, 38, 44, 60, 65, 94, 133, 153, 228, 280, 314, 326, 334, 340, 410, 429, 626, 693, 741, 768, 1150, 1290, 1441, 2424, 2478, 3024, 3293 65 29 1, 3, 5, 11, 17, 21, 29, 47, 85, 93, 129, 151, 205, 239, 257, 271, 307, 351, 397, 479, 553, 1317, 1631, 1737, 1859, 1917, 1999, 2353, 3477 67 26 2, 6, 14, 20, 44, 66, 74, 102, 134, 214, 236, 238, 342, 354, 382, 454, 470, 598, 726, 870, 1148, 1366, 1692, 1782, 1870, 3602 69 17 1, 2, 10, 14, 19, 26, 50, 55, 145, 515, 842, 1450, 2159, 2290, 2306, 2335, 3379 71 14 3, 5, 9, 19, 23, 27, 57, 59, 65, 119, 299, 417, 705, 2255 73 16 2, 6, 14, 24, 30, 32, 42, 44, 60, 110, 212, 230, 1892, 1974, 2210, 3596 75 30 1, 3, 4, 6, 7, 10, 12, 34, 43, 51, 57, 60, 63, 67, 87, 102, 163, 222, 247, 312, 397, 430, 675, 831, 984, 1018, 1054, 1615, 2017, 2157 77 11 3, 7, 19, 23, 95, 287, 483, 559, 655, 667, 1639 79 9 2, 10, 46, 206, 538, 970, 1330, 1766, 2162 81 44 1, 4, 5, 7, 12, 15, 16, 21, 25, 27, 32, 35, 36, 39, 48, 89, 104, 121, 125, 148, 152, 267, 271, 277, 296, 324, 344, 396, 421, 436, 447, 539, 577, 592, 711, 809, 852, 1384, 1972, 2624, 2829, 3497, 3945, 3995 83 9 1, 5, 157, 181, 233, 373, 2425, 2773, 3253 85 18 4, 6, 10, 30, 34, 36, 38, 74, 88, 94, 148, 200, 624, 1300, 2458, 2556, 3638, 3834 87 17 2, 6, 8, 18, 26, 56, 78, 86, 104, 134, 207, 518, 602, 1268, 1302, 2324, 2372 89 11 1, 7, 9, 21, 37, 61, 589, 711, 1537, 1921, 3217 91 4 8, 168, 260, 696 93 27 2, 4, 6, 10, 12, 30, 42, 44, 52, 70, 76, 108, 122, 164, 170, 226, 298, 398, 686, 1020, 1110, 1478, 1646, 2032, 2066, 2800, 2816 95 25 1, 3, 5, 7, 13, 17, 21, 53, 57, 61, 83, 89, 111, 167, 175, 237, 533, 621, 661, 753, 993, 1039, 1849, 1987, 3437 97 12 2, 4, 14, 20, 40, 266, 400, 652, 722, 2026, 2732, 3880 99 33 1, 2, 5, 6, 10, 11, 22, 31, 33, 34, 41, 42, 53, 58, 65, 82, 126, 143, 162, 170, 186, 189, 206, 211, 270, 319, 369, 410, 433, 631, 894, 1617, 2025

The following is a list of the 50 odd k < 1000 for which there is no prime for n £ 10, and giving the lowest such n.

 k n k n k n k n k n 47 583 259 38 383 6393 605 11 773 53 103 16 263 29 389 11 607 12 797 35 143 53 283 30 437 23 631 144 811 16 197 15 335 19 451 12 647 15 827 19 203 13 351 12 467 19 649 22 829 18 211 20 353 21 481 64 689 15 881 1027 217 66 361 28 533 13 733 12 901 12 227 11 367 12 569 15 751 12 913 18 241 36 377 11 587 227 767 23 917 27 257 279 379 14 601 16 769 14 991 16

Table 1.

The following is a list of 104 odd k < 10000 for which there is no prime for n £ 100, giving the lowest such n, if found, and the search limit if not.

 k n k n k n k n 47 583 3331 172 5459 133 8021 119 257 279 3409 106 5483 137 8119 1162 383 6393 3443 3137 5771 167 8245 658 587 227 3529 122 5881 156 8269 1150 631 144 3533 261 5897 (20170) 8423 (8000) 881 1027 3589 118 6319 4606 8479 322 1021 112 3721 444 6353 785 8543 5793 1201 960 3797 315 6379 1014 8573 165 1277 143 3827 207 6439 578 8749 278 1523 145 3829 1230 6677 319 8791 268 1643 1465 3983 389 6719 103 8911 244 1669 230 4189 114 6721 208 8929 1966 1699 426 4283 689 6767 279 8933 261 1727 367 4337 103 6889 326 8957 115 1741 304 4367 715 6911 263 8989 418 1951 132 4429 342 7013 (24160) 9049 262 2033 221 4727 227 7141 128 9053 241 2057 295 4801 752 7201 964 9091 204 2303 189 4847 (12062) 7397 135 9181 136 2423 881 4861 2492 7489 290 9323 3013 2659 110 5207 251 7493 5249 9443 397 2831 105 5297 (12030) 7651 (8000) 9589 370 2897 9715 5359 (12069) 7909 2174 9743 125 2987 123 5371 388 7913 125 9833 253 3061 (17007) 5417 175 7921 156 9931 496 3289 274 5419 170 7957 5064 9953 205

Table 2.

n = 1 gives a prime for 24 out of the 50 values of odd k < 100.

n = 1 gives a prime for 155 out of the 500 values of odd k < 1000.

n = 1 gives a prime for 1136 out of the 5000 values of odd k < 10000.

n = 1 gives a prime for 9006 out of the 50000 values of odd k < 100000.

n = 2 gives a prime for 22 of the 50 values of odd k < 100.

n = 2 gives a prime for 140 of the 500 values of odd k < 1000.

n = 2 gives a prime for 1056 of the 5000 values of odd k < 10000.

n = 2 gives a prime for 8496 of the 50000 values of odd k < 100000.

n = 1 and 2 give a prime for 39 of the 50 values of odd k < 100.

n = 1 and 2 give a prime for 265 of the 500 values of odd k < 1000.

n = 1 and 2 give a prime for 2024 of the 5000 values of odd k < 10000.

n = 1 and 2 give a prime for 16484 of the 50000 values of odd k < 100000.

n = 1 to 10 give a prime for 49 of the 50 values of odd k < 100.

n = 1 to 10 give a prime for 450 of the 500 values of odd k < 1000.

n = 1 to 10 give a prime for 4150 of the 5000 values of odd k < 10000.

n = 1 to 10 give a prime for 38395 of the 50000 values of odd k < 100000.

n = 1 to 100 give a prime for 49 of the 50 values of odd k < 100.

n = 1 to 100 give a prime for 494 of the 500 values of odd k < 1000.

n = 1 to 100 give a prime for 4896 of the 5000 values of odd k < 10000.

n = 1 to 100 give a prime for 48706 of the 50000 values of odd k < 100000.

n = 1 to 1000 give a prime for 50 of the 50 values of odd k < 100.

n = 1 to 1000 give a prime for 498 of the 500 values of odd k < 1000.

n = 1 to 1000 give a prime for 4975 of the 5000 values of odd k < 10000.

n = 1 to 1000 give a prime for 49753 of the 50000 values of odd k < 100000.

A Sierpinski number is an odd number k such that k.2n +1 is composite for all n ³ 1. Sierpinski proved that the set of Sierpinski numbers is infinite, but the smallest examples he provided were of 18 digits. The Sierpinski Problem is the task of finding k0 - the smallest Sierpinski number. In his proof, Sierpinski used a covering set for each number, i.e. a finite set of primes such that every

k.2n +1 is divisible by at least one of the set. The smallest Sierpinski number known is k = 78557, with covering set {3,5,7,13,19,37,73}, though the Sierpinski number k = 271129 has the shortest covering set {3,5,7,13,17,241}, which has been proved to be the unique shortest possible. In attempting to find k0 , which may or may not be 78557, it is of particular interest to identify, for each odd k, values for which there are no primes for small n, and for each of these to keep raising the search limit on n until a prime is found.

The following is a list of 247 odd k < 100000 for which there is no prime for n £ 1000, giving the lowest value of n giving a prime, or the search limit. Note that the search uses trial division to remove as many values of n as possible from consideration, and so a search limit for a given prime is not necessarily a "round" number.

 k n k n k n 383 6393 10223 (8000) 20851 (8000) 881 1027 10583 2689 21143 1061 1643 1465 10967 2719 21167 6095 2897 9715 11027 1075 21181 (12091) 3061 (17007) 11479 1702 21901 1540 3443 3137 12395 1111 22699 (20133) 3829 1230 12527 2435 22727 1371 4847 (12062) 13007 1655 22951 1344 4861 2492 13787 (8000) 23701 1780 5297 (12030) 14027 (8000) 23779 5234 5359 (12069) 16519 3434 24151 2508 5897 (20170) 16817 (8000) 24737 (8000) 6319 4606 16987 2748 24769 1514 6379 1014 17437 1812 24977 1079 7013 (24160) 17597 3799 25171 2456 7493 5249 17629 1094 25339 4438 7651 (8000) 17701 2700 25343 1989 7909 2174 18107 (12278) 25819 (12001) 7957 5064 18203 6141 25861 4848 8119 1162 19021 2608 26269 1086 8269 1150 19249 (18157) 27653 (12344) 8423 (8000) 27923 (8000) 8543 5793 40547 (8000) 28433 (12072) 8929 1966 40553 1077 29629 1498 9323 3013 40571 1673 41809 1402 50693 (8000) 30091 2184 42257 2667 51617 2675 31951 3084 42409 1506 51917 (8000) 32161 (8000) 43429 4290 52771 (8000) 32393 4365 43471 1508 52909 3518 32731 1720 44131 (8000) 53941 (8000) 33661 (8000) 44629 1270 54001 (12115) 34037 1671 44903 (8000) 54739 (8000) 34565 3361 45713 1229 54767 (8000) 34711 (8000) 45737 2375 55459 (8000) 34999 (12273) 46157 (12046) 56543 2501 35987 2795 46159 4790 56731 1172 36781 4824 46187 (8000) 56867 1127 36983 (8000) 46403 3057 57467 1259 37561 (8000) 46471 (8000) 57503 5697 38029 2778 47179 2918 57949 1058 39079 (12249) 47897 (8000) 58243 1136 39241 1120 47911 5568 59569 (8000) 39781 (8000) 48091 1476 48323 1369 80419 1166 60443 (12260) 48833 (8000) 80839 (4397) 60541 (8000) 49219 (8000) 81091 (4631) 60737 1411 81269 (4342) 60829 6398 70261 3048 81857 1399 61519 1290 71417 (8000) 81871 1420 62093 (12016) 71671 (8000) 81919 (4817) 62761 (8000) 71869 5130 82267 2904 63017 (8000) 72197 2171 82283 2469 63379 2070 73189 4278 82549 (4349) 64007 (8000) 73253 6889 82841 1037 64039 2246 73849 1202 82907 1475 65057 (8000) 74191 (8000) 84409 (4349) 65477 5887 74221 4188 84887 1087 65539 1822 74269 (8000) 85013 (4352) 65567 (20154) 74959 4274 85711 (4343) 65623 1746 75841 (12211) 86701 (4375) 65791 2760 76261 2156 86747 (4346) 65971 1224 76759 (8000) 86761 3896 67193 (8000) 76969 3702 86869 (4521) 67607 (18170) 77267 4159 87469 2110 67759 (8000) 77341 5076 87743 (4352) 67831 1720 77521 3336 88007 2843 67913 5773 77899 (12209) 88157 1063 68393 1901 78181 (8000) 88549 (4401) 69107 (8000) 78557 ------- 89003 1285 69109 (12021) 79309 (5221) 89059 (4433) 79817 (4430) 89225 (4384) 79819 1678 89521 1564 79879 1098 89537 1203 90019 3470 93331 (4463) 97621 1820 90047 1403 93443 1277 97697 2139 90527 (4390) 93593 3597 97789 1102 90529 2518 93617 (4570) 98327 2911 90949 2254 94069 (4429) 98431 (4327) 91291 3432 94373 (4420) 98461 1892 91399 1746 94639 2654 98723 1681 91549 (4445) 95791 1088 98749 (4329) 92119 (4521) 96409 1426 99557 2931 92567 (4366) 96983 (4344) 99587 (4394) 92749 1138 97555 (4355) 99739 (4349) 99769 1042

Table 3.

Counts for surviving k values in steps of 10000 are:-

 total n £ 1000 : 25, 21, 24, 18, 25, 18, 26, 26, 30, 34 247 n £ 2000 : 18, 15, 14, 15, 16, 13, 19, 23, 20, 23 176 n £ 3000 : 16, 9, 12, 12, 13, 11, 16, 21, 16, 17 143 n £ 4000 : 14, 7, 12, 10, 12, 10, 16, 18, 15, 14 128

With direct reference to the Sierpinski Problem, only 178 odd k < 78557 survive with no primes of the form k.2n + 1 for n £ 1000, and this drops to 95 for n £ 4000. With further searches concentrated on these values, currently only 69 odd k < 78557 remain unaccounted for, the smallest being 3061. Therefore we can say that 3061 £ k0 £ 78557.

For each of the values of k > 78557 given in Table 3, only the lowest value of n giving a prime, if known, is listed. Since the search was pushed at least to n £ 4000 for each of these, the following large primes were discovered with n > 2000, of which 7 have more than 1000 digits.

 k n 79819 3598 81871 2164, 2956 82267 2904 82283 2469 86761 3896 87469 2110 88007 2843, 2915 90019 3470 90529 2518 90949 2254 91291 3432, 3672 93443 3633 93593 3597 94639 2654 97697 2139 98327 2911 98723 2245 99557 2931

There remain 31odd k in the higher range for which an associated Robinson prime is not known.

As suggested by the above, I have concentrated mainly in the range 78558 < k < 100000. As part of this, I have located all primes of the form k.2n + 1 for 1001 £ n £ 2000. I then extended this search to cover the range 70000 < k < 78556. Both ranges are detailed below.

range 1 : 78558 < k < 100000

range 2 : 70000 < k < 78556

 range of n range 1 count range 2 count 1001 - 1100 2856 1153 1101 - 1200 2715 1066 1201 - 1300 2435 972 1301 - 1400 2204 894 1401 - 1500 2144 839 1501 - 1600 1953 803 1601 - 1700 1875 744 1701 - 1800 1706 677 1801 - 1900 1610 626 1901 - 2000 1596 622 totals 21094 8396

This gives at total of 29490 primes in the combined range.

The following three Fermat divisors that fall within this range were rediscovered and verified.

82165 * 21084 + 1 divides F1082 ; 79707 * 21231 + 1 divides F1225 ; 98855 * 21851 + 1 divides F1849

The highest number of primes for a particular k in the combined search range 70000 < k < 100000, and for 1001 £ n £ 2000, is 12. This occurs at k = 70365. A count of 11 is achieved for the k values 70653, 73413, 84435, 89595 and 91575.