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.

 

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