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 106 4621.76 4532 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.