Searching for Robinson primes amongst k with high Nash weight

The standard, positive, Nash weight of an odd number k is a general measure of the divisibility properties of the associated Robinson numbers k.2n +1. In particular, the higher the Nash weight, the higher the likelihood of finding primes, since less of the k.2n +1 have small prime factors. The calculation of Nash weights using psieve, the Nash-Jobling implementation that runs in the DOS shell of Windows 9x, is reasonably quick, but running the program over large ranges of k becomes a much slower process. In practice, there are alternative methods that may be used to find k with very high Nash weight.

Firstly, we may consider capping the Nash sieve. This is done by restricting the primes used in constructing the sieve so that only those up to a certain limit, and with exponents up to a certain limit, are considered. I have found that a prime limit of 212 = 4096 is most effective in terms of balancing speed with reasonable accuracy, i.e. modified Nash weights closely matching actual Nash weights. With an exponent limit of 28 = 256 (the same as the standard Nash sieve), calculating weights of consecutive odd k is several orders of magnitude faster than psieve. For the results below, the range of exponents that the capped Nash weight is calculated upon is 1 to 10000, as opposed to 100000 to 109999 for the standard weight.

Secondly, we may consider chain weights, i.e. the number of occurrences of chains of a certain length of unsieved exponents, using either the standard or a modified Nash sieve. For instance, the 4-chain weight of k is the number of sequences of length at least 4 amongst exponents n considered over a given range. There are two points to consider. Firstly, it is obvious that a number with a high 4-chain weight will have comparatively high Nash weight, and secondly, that we can use modular arguments to restrict the number of k that have to be considered, for example, a chain of length 4 requires k 15 mod 30. If we preserve the idea of a capped sieve, we can increase speeds further. For numbers with a high chain weight found this way, we may then calculate the actual Nash weights individually. Since this method is faster, we can increase the exponent limit to 212 = 4096. In order to create a more clearly defined distinction to the weight, the range of exponents is 1 to 100000. This lessens the possibility of duplicate scores while not affecting the underlying order.

Comparing these two ways of finding numbers with very high Nash weight for k < 100000, we obtain the following.

capped weight

top 10

capped weight

Nash weight

chain weight

top 10

chain weight

Nash weight

82875

6010

6008

58905

2806

5820

58905

5855

5820

82875

2301

6008

40755

5728

5723

40755

2193

5723

54615

5699

5693

54615

2067

5693

58305

5617

5468

68265

1835

5417

29835

5603

5589

15345

1828

5532

15345

5537

5532

58305

1741

5468

5775

5535

5554

5775

1708

5554

16095

5530

5531

59565

1664

5358

68175

5466

5459

29835

1567

5589


Although there is a substantial similarity in results, the capped weight is a better reflection of the actual Nash weight, though the chain weight method is much faster. However, there is enough of a correlation to be able to enforce the modular arguments relating to chains onto the capped weight method in order to extend the results. Thus, for k < 106, with the restriction k 15 mod 30, we obtain the following.

capped weight

top 10

capped weight

Nash weight

chain weight

top 10

chain weight

Nash weight

186615

6527

6489

186615

3014

6489

884235

6345

6274

877305

2837

6331

877305

6316

6331

58905

2806

5820

82875

6010

6008

748605

2506

5911

988845

5985

5946

884235

2443

6274

748605

5924

5911

853125

2376

5802

268515

5905

5922

396825

2309

5851

546975

5897

5917

82875

2301

6008

396825

5893

5851

478335

2253

5855

478335

5887

5855

988845

2231

5946


Across the two top tens, there are only 12 different values of k. In fact, the two values in the chain weight top ten that do not appear in the capped weight top ten are actually 11th and 12th. Let us now consider searching for Robinson primes amongst these values. To a limit on n of 50000, we have :

186615

 

877305

11524, 11731, 12899, 14211, 14466, 15375, 17152, 18181, 18941, 19086, 20352, 21417, 22328, 28414, 29504, 31546, 33045, 35357, 41299

884235

11863, 12200, 12923, 20141, 21563, 24938, 24947, 25224, 27532, 28958, 33602, 34787, 37031, 39958, 42405, 42937, 46453, 47909

82875

10670, 11212, 15326, 15410, 15872, 18547, 18862, 27730, 29231, 35783, 38347, 40923, 48616

988845

10184, 10588, 12689, 13541, 13970, 18754, 19584, 19709, 20488, 20904, 24849, 25463, 26200, 27236, 35159, 44998, 47766, 49003

268515

10574, 11006, 13533, 14342, 15900, 18997, 20287, 24779, 25906

546975

 

748605

 

478335

 

396825

 

58905

 

853125

 


The breakdown of smaller Robinson Primes, with n 10000, for the above numbers, is as follows:

k

1 to 100

101 to 1000

1001 to 10000

total

186615

20

17

29

66

877305

18

22

30

70

884235

20

14

26

60

82875

20

17

30

67

988845

20

23

23

66

268515

12

13

27

52

546975

17

17

26

60

748605

20

22

18

60

478335

23

23

21

67

396825

17

14

20

51

58905

19

22

17

58

853125

16

15

24

55

total

222

 

291

732


The existing restriction to k 15 mod 30 is associated with the fact that 3 and 5 are primitive roots modulo 2, and therefore for k to have a chain of length at least 2, k must be divisible by 3, and for k to have a chain of length at least 4, k must be divisible by 5. Restrictions can also be made with respect to 7. Since the exponent of 7 modulo 2 is 3, 7 is not a primitive root, and we cannot simply expect k to be divisible by 7. In fact, 3-chains of the 1st kind can occur for k 0, 3, 5, and 6 mod 7 and of the 2nd kind for k 0, 1, 2, or 4 mod 7. Including divisibility by 3 and 5, these become k 45, 75, 105, 195 mod 210 for the 1st kind and k 15, 105, 135 or 165 mod 210 for the 2nd kind. For a more detailed argument, see the related article on Cunningham chains. Examining the values of k in the above table, we discover that 7 of the top 10, including the top 4, all have k 135 mod 210. Assuming, without justification, that there is something significant about this condition, we proceed for k < 107 using the capped weight method.

capped weight
top 10

capped weight

Nash weight

7844265

6693

6551

186615

6527

6489

6123315

6445

6450

5742165

6438

6379

3048705

6390

6408

884235

6345

6274

2288715

6342

6299

877305

6316

6331

3009435

6263

6247

3986775

6260

6199


The value k = 82875 comes in 17th in this sequence. The 11th to 16th are as follows.

k

capped weight

Nash weight

6462885

6120

6105

1300455

6115

6106

4300725

6078

5997

5116155

6074

6051

6608415

6033

6000

5469585

6028

5976


To give some idea of the general trend regarding Nash weights, we can compare the average values over large ranges. In all the following, the case k = 1 is excluded since the divisibility arguments pertaining to Nash congruences do not apply. The average standard Nash weight for all k < 104 is 1755.32, while the average capped weight obtained in the above manner and over the same range is 1764.09. This slight difference may be a result of occasional irregularities when n is small. The average capped weight for all k < 105 is 1759.83.

Restricting to k 15 mod 30, average capped weights are as follows:

k < 104 : 3323.50

k < 105 : 3299.98

k < 106 : 3300.58

Further restricting to k 135 mod 210 gives the following averages:

k < 104 : 3872.94

k < 105 : 3858.37

k < 106 : 3849.80

k < 107 : 3850.35

Further restrictions may be imposed, for example, 9 of the top 10 with k 135 mod 210 have k divisible by 11 and 7 are divisible by 13. If we restrict k to be divisible by 11, then the congruence becomes k 1815 mod 2310. The averages in this case are as follows:

k < 104 : 4446.50

k < 105 : 4282.14

k < 106 : 4244.89

k < 107 : 4236.23

k < 108 : 4235.70

We can use 11 in this way since it is a primitive root modulo 2 and so can be used in a search for numbers with a high 10-chain weight, which will obviously have high Nash weight. The new top ten is as follows:

capped weight
top 10

capped weight

Nash weight

56883255

6725

6690

15952365

6708

6706

7844265

6693

6551

91627965

6578

6475

10246665

6566

6422

53730105

6546

6542

97566975

6535

6534

96222555

6532

6525

186615

6527

6489

6123315

6445

6450


For k 1815 mod 2310, 8 of the top 10 are divisible by 13, including the top 6. Since 13 is also a primitive root modulo 2, this suggests numbers with high 12-chain weight. Restricting k to be divisible by 13 gives the new congruence k 6435 mod 30030. The new top ten is:

capped weight
top 10

capped weight

Nash weight

333729825

7034

7054

736402095

6846

6821

978173625

6844

6855

102438765

6776

6760

805320945

6752

6747

247423605

6748

6749

56883255

6725

6690

15952365

6708

6706

298354485

6707

6711

191387625

6698

6712


and the averages are:

k < 105 : 4454.00

k < 106 : 4690.15

k < 107 : 4602.97

k < 108 : 4590.51

k < 109 : 4588.48

In the above, it was suggested that the values k 135 mod 210 were most appropriate to study. However, if we choose k 165 mod 210, there is promise of more numbers with very high Nash weight. Combining this congruence with the recommended restriction that k is divisible by both 11 and 13 gives k 27885 mod 30030. The top 10 for k < 109 with this condition are as follows:

capped weight
top 10

capped weight

Nash weight

986963835

7232

7237

723630765

6804

6757

935252175

6797

6806

229757385

6797

6794

450387795

6768

6724

930477405

6765

6790

749066175

6751

6759

919096035

6744

6729

734291415

6728

6558

171649335

6705

6704


and the averages are:

k < 105 : 4348.33

k < 106 : 4605.61

k < 107 : 4582.50

k < 108 : 4586.43

k < 109 : 4588.47

This last is within 0.01 of the value for k 6435 mod 30030, and, in general, over the largest range the two congruences perform almost identically. This suggests the same may be true for the k 15 mod 210 case, which becomes k 10725 mod 30030 with the additional restrictions. This was also checked to 109 and the following obtained:

capped weight
top 10

capped weight

Nash weight

302442855

7033

6999

806586495

6943

6825

63374025

6878

6749

24094785

6848

6846

765745695

6844

6847

407427735

6822

6803

515866065

6790

6776

170701245

6768

6756

328869255

6726

6706

562622775

6724

6705


and the averages are:

k < 105 : 4775.00

k < 106 : 4488.73

k < 107 : 4580.71

k < 108 : 4585.97

k < 109 : 4588.36

For completeness, the k 105 mod 210 condition, which becomes k 15015 mod 30030, was tested over the same range to give the following :

capped weight
top 10

capped weight

Nash weight

302627325

7091

7093

614578965

6915

6897

362026665

6901

6894

981095115

6876

6877

466440975

6817

6739

994218225

6809

6816

963077115

6801

6785

959653695

6736

6688

24459435

6734

6727

463948485

6706

6662


and the averages are:

k < 105 : 4490.00

k < 106 : 4611.55

k < 107 : 4598.10

k < 108 : 4589.92

k < 109 : 4588.57

It is no surprise that over the very large ranges covered, the 4 congruences perform identically. The combined top 10 over all 4 congruences is :

capped weight
top 10

capped weight

Nash weight

986963835

7232

7237

302627325

7091

7093

333729825

7034

7054

302442855

7033

6999

806586495

6943

6825

614578965

6915

6897

362026665

6901

6894

63374025

6878

6749

981095115

6876

6877

24094785

6848

6846


The breakdown of small Robinson primes for the k with highest Nash weights is:

k

cap weight

1 to 100

101 to 1000

1001 to 10000

total

986963835*

7232

18

25

30

73

302627325*

7091

22

23

26

71

333729825

7034

12

20

31

63

302442855*

7033

17

31

38

86

806586495*

6943

15

20

24

59

614578965

6915

14

15

29

58

362026665

6901

27

20

31

78

63374025

6878

19

27

33

79

981095115*

6876

19

24

30

73

24094785*

6848

16

20

27

63

736402095

6846

15

20

21

56

978173625

6844

17

20

30

67

765745695

6844

14

35

33

82

407427735

6822

16

28

25

69

466440975

6817

15

22

20

57

994218225

6809

19

22

34

75

723630765

6804

18

27

26

71

963077115

6801

20

25

15

60

935252175

6797

15

23

36

74

229757385

6797

15

16

23

54

515866065

6790

17

22

23

62

102438765*

6776

18

29

20

67

450387795

6768

17

27

26

70

170701245

6768

13

16

29

58

930477405

6765

14

19

25

58

805320945

6752

11

23

26

60

749066175

6751

19

27

31

77

247423605

6748

16

18

20

54

919096035

6744

15

25

28

68

959653695

6736

18

22

30

70

24459435

6734

12

16

34

62

734291415

6728

20

20

29

69

328869255

6726

18

23

30

71

56883255

6725

16

22

33

71

562622775

6724

15

24

29

68

640160235

6722

13

15

26

54

156256815

6714

15

24

16

55

15952365*

6708

14

8

27

49

298354485

6707

20

30

24

74

463948485

6706

19

26

21

66

171649335

6705

18

25

14

57

191387625

6698

19

25

23

67

166166715

6698

15

25

24

64

901030845

6697

15

25

25

65

109886205

6695

20

35

22

77

7844265

6693

24

29

31

84

382116735

6692

17

19

22

58

49354305

6691

16

22

28

66

344999655

6691

15

32

18

65

620095905

6681

16

24

28

68

335861955

6677

20

15

17

52

96467085

6675

12

20

27

59

577294575*

6674

28

28

39

95

250688295

6674

14

26

21

61

373227855

6673

15

25

25

65

805402455

6672

17

21

20

58

295621755

6672

16

22

32

70

248873625

6672

19

15

30

64

219864645

6667

14

27

17

58

865024875

6665

12

19

17

48

160190745

6659

17

25

34

76

60208005

6658

19

15

22

56

989224665

6657

19

14

31

64

393571035*

6656

21

31

22

74

852142005

6655

18

33

29

80

959739495

6654

15

21

25

61

901631445

6654

15

19

33

67

298483185

6653

18

21

26

65

213978765

6653

14

21

28

63

594278685

6652

17

19

21

57

430160445

6652

16

24

19

59

213133635

6652

17

24

27

68

totals

 

1211

1645

1886

4742


In the above table, k values marked with an asterisk are being actively searched for large primes by others. For current progress, see Caldwell's complete listing of large primes.

 
Exactly analogous arguments may be used to locate Robinson numbers of very high negative Nash weight. The 4 related congruences become k 2145, 15015, 19305 and 23595 mod 30030 when 11 and 13 are included. The averages are :

k limit

2145

15015

19305

23595

105

4828.75

4555.33

4900.33

4405.00

106

4621.76

4532.00

4645.42

4547.06

107

4585.87

4586.63

4600.69

4574.32

108

4584.91

4589.41

4589.68

4590.29

109

4588.01

4588.64

4588.78

4588.47


The combined negative top 10 is :

capped weight
top 10

capped weight

Nash weight

120023475

7074

7061

387376275

7040

6970

768216735

6991

6971

115029915

6990

6966

413468055

6984

6982

464857965

6969

6936

290499495

6962

6961

666625245

6919

6829

351374595

6919

6915

245630385

6914

6864


The breakdown of small Robinson primes for the k with highest negative Nash weights is:

k

cap weight

1 to 100

101 to 1000

1001 to 10000

total

120023475

7074

17

26

27

70

387376275

7040

17

25

36

78

768216735

6991

14

20

34

68

115029915

6990

19

26

30

75

413468055

6984

17

25

39

81

464857965

6969

16

17

21

54

290499495

6962

27

21

27

75

666625245

6919

11

24

30

65

351374595

6919

18

23

25

66

245630385

6914

18

33

29

80

244716615

6909

17

21

35

73

475977645

6905

16

19

26

61

97102005

6877

15

27

23

65

532751505

6863

15

26

20

61

775784295

6856

21

15

23

59

539641245

6847

13

25

25

63

736320585

6841

14

17

32

63

727238655

6817

13

26

19

58

869688105

6816

17

24

27

68

825273735

6796

20

11

39

70

585063765

6795

13

20

26

59

504017085

6785

11

35

25

71

261850875

6779

19

21

23

63

124828275

6778

15

20

31

66

443995695

6770

17

20

26

63

880923615

6766

15

17

24

56

177917025

6758

16

19

28

63

509070705

6756

14

20

23

57

959657985

6754

11

21

34

66

902613855

6750

12

22

31

65

680872335

6749

15

22

25

62

274973985

6731

19

29

22

70

657569055

6729

17

14

32

63

404643525

6729

20

22

26

68

707710575

6728

17

16

27

60

252631665

6713

10

19

23

52

959760945

6705

14

16

25

55

129723165

6704

15

21

22

58

355424355

6703

13

21

32

66

236411175

6696

13

26

28

67

190053435

6694

19

26

28

73

164283405

6694

12

15

29

56

504793575

6693

9

23

28

60

308731995

6693

26

26

22

74

949473525

6690

20

26

30

76

461164275

6689

13

22

19

54

790361715

6687

12

20

32

64

368997915

6687

18

25

19

62

324437685

6687

19

23

15

57

304369065

6680

18

22

17

57

451035585

6678

16

25

24

65

940404465

6670

16

17

30

63

243022065

6669

14

16

32

62

54896985

6668

15

25

25

65

78127335

6664

22

21

20

63

653785275

6661

16

26

20

62

622343865

6661

18

18

21

57

294956805

6655

19

23

25

67

totals

 

933

1271

1536

 


The positive and negative modified Nash weights were calculated for all odd k < 105. Of particular interest are those k that score highly on both counts. There are 17 values of k for which both weights are at least 4500. Of these, two, namely 25935 and 58905, have a combined weight, obtained by adding the weights together, in excess of 10000. The congruence k 15 mod 30 was used to a limit of 106. There are 16 values of k in this range that have both weights at least 5000, of which 4, namely 435435, 592515, 664125 and 945945 have a combined score greater than 11000. To a limit of 109, the common congruence k 15015 mod 30030 produces 14 values of k for which both weights are at least 6000, including 6 that have a combined score greater than 12500. The highest combined score was 12813 at k = 137792655. Such values of k may be thought of potential sources of very large twin primes.

URL : www.glasgowg43.freeserve.co.uk/nashprim.doc