A search for very low Nash weights

I have previously used a convenient method for finding numbers with low Nash weight. This consists of counting the number of times that the Robinson numbers k.2n + 1 for n between 1 and 1000 do not succumb to trial division by the primes less than 2000. If this count exceeds 10 then the value of k is discarded, otherwise I calculate the Nash weight. I first extended this idea for all odd k less than 107. This provides the following data (where NW(k) is used as shorthand for the Nash weight).

 k range (million) NW(k) < 100 NW(k) ³ 100 total 0 - 1 134 232 366 1 - 2 114 226 340 2 - 3 124 222 346 3 - 4 120 227 347 4 - 5 111 238 349 5 - 6 115 250 365 6 - 7 129 220 349 7 - 8 123 213 336 8 - 9 121 236 357 9 - 10 140 221 361 totals 1231 2285 3516

Alternatively, we can count the under / over 100 split for each intermediate weight, as follows.

 weighting count NW < 100 NW ³ 100 %age #1 %age #2 0 69 69 0 100 1.96 1 10 10 0 100 0.28 2 19 19 0 100 0.54 3 60 60 0 100 1.71 4 97 94 3 96.91 2.76 5 191 159 32 83.25 5.43 6 281 196 85 69.75 7.99 7 371 195 176 52.56 10.55 8 598 219 379 36.62 17.01 9 827 138 689 16.69 23.52 10 993 72 921 7.25 28.24 totals 3516 1231 2285

The first percentage above is of NW < 100 against total for that weighting, (column 3 against column 2) and the second percentage is of the particular weighting (column 2 ) against the total number of k considered.

From the above data, it can be seen that the return in terms of number of values with a Nash weight less than 100 peaks at a weighting of 8 and tails off for 9 and 10. Since these take extra time to locate and account for more than half of the total, any additional searches will in future restrict the intermediate weighting further in order to speed things up and reduce the volume of data to be considered. Since in the current range, the lowest Nash weights found for weightings 9 and 10 are 67 and 73 respectively, it is unlikely that a Nash weight of less than 50 will be overlooked by this restriction.

There were 69 values of k found with a Nash weight of zero. These have all been verified as Sierpinski numbers. Apart from these, the lowest Nash weights found in the range being considered were as follows.

 k weighting Nash weight 3203597 1 25 1763963 2 26 6729197 2 26 4775903 2 30 7662049 1 31 7755317 2 31 4011923 5 31 957977 2 32 1803107 3 32 9178231 * 6 32 285601 3 33 8269523 * 1 34 7861411 * 3 35

Nash weights as low as this are striking and indicate the possibility of Sierpinski numbers with infinite covering sets, a concept about which little is known at present. However, each of the above was checked for n £ 10000, and the numbers marked with an asterisk have associated Keller primes for n = 4, 2193 and 28 respectively. A very low Nash weight, by itself, is therefore no absolute guarantee of the Sierpinski property, and suggests that additional forces are at work.

Consider k = 3203597. A quick check reveals that the only values of n up to 8000 for which k.2n +1 is not divisible by a prime less than 2000 are as follows.

 n factors of k.2n +1 747 362353 3650117 1107 24413 1179 561359 1630813 1467 40411823 2619 18397 3987 4059 5139 17923 5499 15649 6579 7299 94153 7659 495139

The factors above were found relatively quickly using either a straight sieve or Pollard's (p- 1)-method. This list can be extended by using Gallot's proth.exe program with the appropriate settings. Including the three above, there are only 72 values of n £ 100000 that require to be fully tested to determine their nature.

The latest version of psieve.exe includes parameters -ya and -zb which redefine the sieve range to start at a and to run across b consecutive values. The standard Nash weight is obtained using a = 100000 and b = 10000. If we take a = 1 and b = 100000, we get a more sensitive measure of the effectiveness of the sieve.

 sieve limit Nash weight extended Nash weight 256 25 257 512 24 244 1024 20 192

Extending the search to 2*107 but with a limit of 8 on the intermediate weighting provides the following cumulative results.

 weighting count NW < 100 NW ³ 100 %age #1 %age #2 0 138 138 0 100 3.98 1 19 19 0 100 0.55 2 42 41 1 97.62 1.21 3 122 122 2 98.36 3.52 4 207 197 10 95.17 5.98 5 390 335 55 85.90 11.26 6 551 393 158 71.32 15.91 7 794 415 379 52.27 22.92 8 1201 390 811 32.47 34.67 totals 3464 2048 1416

Of the values with intermediate weighting of 0, one, that is, k = 13965257, has a non-zero Nash weight of 34 and is not a Sierpinski number. Other numbers of very low Nash weight include the following.

 k weighting Nash weight 19989199 1 19 16002271 2 27 16426793 1 27 18546533 5 29 11317157 2 30 18386297 3 31 19430753 2 31 11903153 3 32 13884527 3 32 13434683 2 33 17429963 3 33 17531569 1 33 12317507 * 3 34 13965257 * 0 34 14260907 * 5 34 15700613 * 4 34

The marked numbers have Keller primes for n = 947, 7263, 3 and 93 respectively with searches limited to n £ 10000.

Consider k = 19989199. The only values of n up to 8000 for which k.2n +1 is not divisible by a prime less than 2000 are the following.

 n factors of k.2n +1 326 2269 8641 15731 372352249 313981739987 1046 7075933 2342 13451 3062 7121 3782 82807979 4502 4646 8641 5222 5366 291547 5942 71999 119027 6662 1749151 6806

Including the three above, there are only 65 values of n £ 100000 that require to be fully tested by proth.exe to determine their nature. With the different sieve limits, we obtain the following values.

 sieve limit Nash weight extended Nash weight 256 19 182 512 17 164 1024 17 147

Extending the search to 5*107 but with a limit of 6 on the intermediate weighting provides the following cumulative results.

 weighting count NW < 100 NW ³ 100 %age #1 %age #2 0 334 334 0 100 9.32 1 30 30 0 100 0.84 2 95 93 2 97.89 2.65 3 267 263 4 98.50 7.45 4 528 502 26 95.08 14.74 5 941 807 134 85.76 26.26 6 1388 1008 380 72.62 38.74 totals 3583 3037 546

Another value with intermediate weighting of 0, that is, k = 47794969, has a non-zero Nash weight of 37 and is not a Sierpinski number. Other numbers of very low Nash weight include the following.

 k weighting Nash weight 46082329 1 16 41612693 3 17 29607287 * 2 20 36029843 3 21 43726457 * 3 23 28245713 * 3 24 29164099 1 24 24444559 2 25 37424581 * 2 25 20035609 3 26 31280087 4 26 43936787 * 4 26 27129709 2 27 29053043 3 27 32898571 2 27 41469949 3 27 35365727 2 28 39533989 4 28

The marked numbers have Keller primes for n = 455, 475, 409, 724 and 67 respectively with searches limited to n £ 10000. The value k = 29607287 is remarkable since as well as providing a prime for n = 455, it also provides a prime for n = 9383. Similarly, k = 43936787 provides a prime for n = 355 as well as n = 67.

Consider k = 46082329. The only values of n up to 8000 for which k.2n +1 is not divisible by a prime less than 2000 are the following.

 n factors of k.2n +1 710 1430 2006 6143 2150 33091907 2726 4007 4310 4886 124717 3443131 5030 17255509 5750 6326 59083 71347 7190 7766 7910

Including the seven above, there are only 51 values of n £ 100000 that require to be fully tested by proth.exe to determine their nature. With the different sieve limits, we obtain the following values.

 sieve limit Nash weight extended Nash weight 256 16 157 512 14 148 1024 14 140

Extending the search all the way to 108 with a limit of 5 on the intermediate weighting provides the following cumulative results.

 weighting count NW < 100 NW ³ 100 %age #1 %age #2 0 683 683 0 100 15.72 1 62 62 0 100 1.43 2 204 202 2 99.02 4.7 3 489 481 8 98.36 11.25 4 1046 992 54 94.84 24.07 5 1861 1572 289 84.47 42.83 totals 4345 3992 353

Another 4 values were found with an intermediate weighting of zero but a non-zero Nash weight. Other numbers of very low Nash weight include the following.

 k weighting Nash weight 57159653 * 3 15 61340537 0 22 80761943 * 2 23 98335907 4 23 91693411 3 24 63372349 4 25 63064307 1 26 95081341 1 26 74885599 * 5 27 79462081 1 28 82110257 3 28 91807141 3 28 93599791 4 28 99505909 * 3 28

The marked numbers have Keller primes for n = 49, 57, 198 and 770 respectively with searches limited to n £ 10000.

Consider k = 57159653. The only values of n up to 8000 for which k.2n +1 is not divisible by a prime less than 2000 are the following.

 n factors of k.2n +1 49 prime 409 4099 60689 14147773487 769 2179 12953 49253 1849 3049 5153 2209 2929 4637 3289 22511 4009 4369 2309 4729 302897237 5809 8123 17137 6889 5153 7609

Including the three above, there are only 50 values of n £ 100000 that require to be fully tested by proth.exe to determine their nature. With the different sieve limits, we obtain the following values.

 sieve limit Nash weight extended Nash weight 256 15 152 512 13 144 1024 13 134

Extending the search to 2*108 with a limit of 4 on the intermediate weighting provides the following cumulative results.

 weighting count NW < 100 NW ³ 100 %age #1 %age #2 0 1350 1350 0 100 26.98 1 116 116 0 100 2.32 2 419 416 3 99.28 8.37 3 1006 990 16 98.41 20.11 4 2112 1992 120 94.32 42.21 totals 5003 4864 139

Another 3 values were found with an intermediate weighting of zero but a non-zero Nash weight. Other numbers of very low Nash weight include the following.

 k weighting Nash weight 166851887 2 9 153810901 1 15 166998751 1 17 188159177 2 18 195242543* 2 18 199816231 0 18 132009197 2 19 164822573 1 19 199148179 1 20 104921599 2 21 120781021 2 21 148068563 0 21 185005433 2 21

The marked number has a Keller prime for n = 997. All the above values of k were searched to a limit of n £ 10000.

Consider k = 166851887. The only values of n up to 8000 for which k.2n +1 is not divisible by a prime less than 2000 are the following.

 n factors of k.2n +1 251 10624251910099 491 173137781 21265517935609 4811 6971

Including the two above, there are only 28 values of n £ 100000 that require to be fully tested by proth.exe to determine their nature. With the different sieve limits, we obtain the following values.

 sieve limit Nash weight extended Nash weight 256 9 111 512 7 82 1024 6 79

Extending the search to 5*108 with a limit of 2 on the intermediate weighting provides the following cumulative results.

 weighting count NW < 100 NW ³ 100 %age #1 %age #2 0 3364 3364 0 100 72.25 1 280 278 2 99.29 6.01 2 1012 1002 10 99.01 21.74 totals 4656 4644 12

There were 16 additional values with an intermediate weighting of zero but a non-zero Nash weight. Although no value bettered the Nash weight of 9 given above, the following have very low Nash weight.

 k weighting Nash weight 200973421 0 11 207372917 2 12 208200121 2 12 278261611 0 12 472628029 2 14 236258329 1 15 346876883* 1 15 279144421 0 16 330361951 1 16 441280831 2 16 284565529 2 18 317697113 1 18 459974371* 1 18 462175489 2 18 479290223 2 18 234332251 1 19 345127459 1 19

The marked numbers have Keller primes for n = 1977 and 4076 respectively with searches limited to n £ 10000.

The total number of k values found with Nash weight less than 20 is 29, all of which are listed above. For completeness, the next table gives numbers of k found with Nash weights in the given ranges.

 0 1 to 9 10-19 20-29 30-39 40-49 50-59 60-69 70-79 80-89 90-99 1-99 3339 1 28 205 536 881 1294 1456 1355 1232 1149 8137

Note that the counts drop off because of the increasing restrictions applied to the search.