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.2^{n} + 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 10^{7}. 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.2^{n} +1 is not divisible by a prime less than 2000 are as follows.
n 
factors of k.2^{n} +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*10^{7} 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 nonzero 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.2^{n} +1 is not divisible by a prime less than 2000 are the following.
n 
factors of k.2^{n} +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*10^{7} 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 nonzero 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.2^{n} +1 is not divisible by a prime less than 2000 are the following.
n 
factors of k.2^{n} +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 10^{8} 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 nonzero 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.2^{n} +1 is not divisible by a prime less than 2000 are the following.
n 
factors of k.2^{n} +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*10^{8} 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 nonzero 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.2^{n} +1 is not divisible by a prime less than 2000 are the following.
n 
factors of k.2^{n} +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*10^{8} 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 nonzero 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 
1019 
2029 
3039 
4049 
5059 
6069 
7079 
8089 
9099 
199 
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.