Searching for large Robinson primes using values of k with low Nash weight

The (standard) Nash weight of an odd number k is the number of unsieved values of n remaining over the range 100000 £ n < 110000 after performing a Nash sieve with a (default) exponent limit of 256 on numbers of the form k.2ⁿ +1. For values of k with a low Nash weight (less than 200), the number of exponents surviving the trial division stage of Gallot's implementation of Proth's Test is very low, with sometimes several hundred consecutive exponents being skipped. This allows me to push the lower search limit on the exponents much higher than normal in a comparatively short time.

The greatest interest is in values for which the Nash weight is less than 100. These are comparatively rare, and the relatively slow process of calculating Nash weights for large ranges of consecutive values of k encourages us to consider alternatives.

Numbers with low Nash weight are found during investigation into the Sierpinski problem. A Sierpinski number is a value of k for which no prime exists of the form k.2ⁿ +1 for any n. The Sierpinski problem is generally viewed as the process of eliminating values of k as possible Sierpinski numbers by finding very large primes of the form k.2ⁿ +1 for those k that do not succumb easily to trial division. As a precursor to this, it is a relatively quick process to list all k in a range for which there is no Robinson prime with n £ 1000 (there are typically 25 of these in a 5000 element range). The Nash weights of each k of this type can be calculated individually, and, by their nature, fall typically towards the low end of the weight spectrum. In particular, Nash weights of less than 100 occur with greater frequency than the norm.

However, to use this as the only source would be to ignore a large number of low Nash weight k for which one or two small Robinson primes do exist. An alternative is as follows. First, we shall ignore any odd number which is divisible by either 3, 5 or 7. This condition was applied after an examination of existing numbers known to be of low Nash weight, and immediately and substantially reduces the search space. For each surviving k, we run through the Robinson exponent n from 1 to 1000, sieving across the primes less than 2000 (or the square root of k.2ⁿ +1, whichever is smaller). The number of exponents n for which k.2ⁿ +1 survives this trial division indicates the number of times that the Proth Test would be required in order to prove whether or not k.2ⁿ +1 is prime. This may be considered an alternative weighting index for k. If this index ever exceeds 10, then we immediately ignore k. The Nash weights of surviving k are calculated explicitly, and are often less than 100. The limit of 10 on the intermediate weighting index was obtained by observation: none of the first 28 values of k with an index of 11 have Nash weight less than 100.

I have performed this check for all odd k less than one million. This produces 366 values, of which 203 have no prime for n £ 1000 and so may be ignored as they are investigated elsewhere. Although this is a substantial overlap with values of k with low Nash weight found via the Sierpinski problem, there is sufficient bonus to make this method worthwhile.

The following results were obtained by applying Gallot's proth.exe to the remaining 163 values of k, for which there is at least one prime for n £ 1000, and of which 46 have Nash weight less than 100. We list k, the index of k defined above, the Nash weight, and exponents that provide primes, with the current search limit on exponents following in brackets.

18619 10 156 790, 13294 (40000)

22193 8 113 501, 9741 (40000)

23971 9 108 8 (40000)

25759 10 120 46 (40000)

28943 8 156 505 (40000)

29333 10 120 893 (40000)

32449 10 134 698 (40000)

37231 10 109 16, 2416 (40000)

41693 10 166 33, 73, 12073 (40000)

50839 8 123 6 (40000)

51173 3 44 29, 3089 (75000)

55849 7 116 542 (40000)

59447 8 135 123, 531, 819 (40000)

60413 6 94 369 (60000)

60961 10 109 588 (50000)

61703 6 107 1, 15337, 32257 (50000)

70381 10 152 752, 1808 (40000)

76877 5 96 11 (60000)

85937 9 127 87, 14895 (40000)

89101 10 111 196 (40000)

94127 10 118 555, 651, 5595, 11883, 19587 (40000)

95689 10 184 194 (40000)

97681 9 128 20, 68 (40000)

103787 9 97 7, 23407 (65000)

105811 9 140 176 (40000)

112073 5 112 17, 257, 33857 (40000)

127501 7 77 48 (70000)

129293 8 68 29, 34869 (70000)

139613 10 126 57, 3657 (40000)

139667 9 133 95 (40000)

145127 10 109 59 (40000)

151849 10 132 834, 28734 (40000)

156859 8 127 134, 2006, 5858, 14642 (40000)

157351 10 132 4, 1444, 16996 (40000)

157849 7 86 862 (60000)

158387 10 148 67 (40000)

168173 6 66 577, 7537 (70000)

196607 8 93 895, 1279 (70000)

204137 9 126 363, 3495 (40000)

204797 7 113 547 (40000)

210377 10 153 7, 3175, 10687, 18031, 19879 (40000)

227449 10 155 82 (40000)

228289 9 107 18, 25362 (50000)

238171 9 181 56, 13608 (40000)

239987 8 119 11, 443, 2459, 2939 (40000)

241141 8 85 348 (60000)

244711 6 87 232 (60000)

256021 10 121 104, 33920 (40000)

257869 10 94 2, 242 (60000)

258319 6 99 54 (60000)

260993 8 74 313 (70000)

265943 8 144 37 (40000)

272149 8 91 618, 8730, 46698 (60000)

286397 8 75 59, 491, 683 (70000)

291497 9 93 219, 315, 2331 (60000)

294143 9 147 89 (40000)

295277 10 126 275, 4775, 5855, 10895 (40000)

318233 8 95 29, 101, 869, 3509 (60000)

325037 8 111 523 (50000)

331637 10 97 3, 111, 723, 4431, 34311 (60000)

337907 8 84 27, 387, 2691, 2763 (65000)

342949 10 169 30, 66 (40000)

351139 8 111 6, 294 (50000)

367069 10 114 2, 266, 1406, 39926 (50000)

393287 9 92 7 (60000)

393977 8 147 183, 551, 2423 (40000)

398963 9 120 705 (40000)

400039 7 85 102, 138 (60000)

404179 8 137 62, 31334 (40000)

404207 8 119 187 (40000)

410959 8 126 138, 1218, 4998, 15294 (40000)

415861 7 121 804 (40000)

452567 8 87 3 (60000)

457981 9 113 56, 22160 (50000)

458761 9 150 44, 60, 1484 (40000)

467417 10 172 7 (40000)

468961 9 90 20, 236 (60000)

478651 7 106 84 (50000)

486293 7 70 69, 57309 (70000)

497761 9 128 312, 1992 (40000)

499337 3 64 11 (75000)

504061 8 135 4 (40000)

505669 9 140 678 (40000)

506183 9 95 37, 2965, 54085 (60000)

509897 9 125 615 (40000)

517411 9 123 4 (40000)

544171 10 107 768 (50000)

545971 10 113 4 (50000)

551207 5 91 11, 50231 (60000)

558227 5 70 171 (70000)

559789 8 93 2 (60000)

560957 10 141 39, 231 (40000)

565463 9 109 273 (50000)

571471 10 116 12 (45000)

589819 7 51 158 (80000)

589847 8 89 43, 379 (60000)

599569 9 141 18, 66 (45000)

618439 5 57 90 (80000)

625337 10 130 31, 115 (40000)

636257 7 79 91, 235 (70000)

636991 7 104 816, 12120 (50000)

641903 10 205 153, 1125, 5301, 12501 (40000)

656899 10 112 78 (50000)

670921 8 166 740 (40000)

676009 9 95 198, 30798 (60000)

679279 7 133 166 (40000)

686971 10 107 376 (50000)

693353 10 86 93 (60000)

707041 9 102 124 (40000)

709547 9 135 191 (40000)

710183 8 115 141, 429, 4821 (50000)

714769 10 196 22, 478 (40000)

720887 10 115 79, 20575, 37567 (50000)

723617 6 67 475 (80000)

733381 10 163 64, 280, 28288 (40000)

734807 9 154 11, 467, 21635 (40000)

737147 8 127 31 (50000)

738743 10 142 253, 1957 (40000)

742307 10 90 23, 64535 (70000)

777353 10 129 17, 977, 16433 (50000)

778951 6 82 144 (100000)

782087 10 141 543 (40000)

791447 10 132 23, 383, 22127, 23855 (40000)

803003 7 95 45 (70000)

804079 6 105 210, 1578 (60000)

804653 10 125 233, 25721 (50000)

808247 10 139 43, 10987, 17647 (40000)

809633 6 132 341, 2717, 8285 (40000)

812509 9 129 18, 954, 36414 (40000)

814789 6 80 74 (80000)

815239 10 151 294, 486, 822 (40000)

820861 10 158 44, 524, 3788 (40000)

821117 9 131 63, 16287 (40000)

828049 9 146 106, 682, 6178 (40000)

831619 8 90 18, 90, 1290 (70000)

836687 7 92 3 (70000)

842957 9 149 603, 26199 (40000)

844819 8 130 758 (40000)

852529 10 108 250, 5602 (50000)

859669 8 225 106, 194, 3586, 21794 (40000)

860117 9 100 7 (60000)

860851 10 130 60, 420, 19236 (40000)

869273 10 107 73 (60000)

872177 7 89 15 (70000)

874459 8 122 82 (40000)

896341 10 112 12, 84 (50000)

897473 10 186 89, 1505, 20729, 33209 (40000)

898397 10 121 507 (40000)

900409 8 141 94 (40000)

901039 9 122 2, 290 (40000)

914689 9 137 254 (40000)

916471 10 100 240 (50000)

926929 6 97 6, 7398 (60000)

935093 10 154 373 (40000)

936743 8 137 9, 4689 (40000)

979457 9 112 15 (50000)

980507 10 147 107, 1475, 2747 (40000)

980731 9 135 624, 1080, 4208, 6168 (40000)

983089 9 149 58, 490, 7258 (40000)

983153 6 89 153, 345, 1161, 4665, 6345 (70000)

984049 10 129 38, 86, 18470 (40000)

987647 7 112 987 (50000)

991217 10 142 35, 995, 4563 (40000)

URL : www.glasgowg43.freeserve.co.uk/nash.htm