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.2ⁿ +1. In particular, the higher the Nash weight, the higher the likelihood of finding primes, since less of the k.2ⁿ +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 2¹² = 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 2⁸ = 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 2¹² = 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.

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 < 10⁶, with the restriction k º 15 mod 30, we obtain the following.

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 11^th and 12^th. Let us now consider searching for Robinson primes amongst these values. To a limit on n of 50000, we have :

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

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 1^st kind can occur for k º 0, 3, 5, and 6 mod 7 and of the 2^nd 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 1^st kind and k º 15, 105, 135 or 165 mod 210 for the 2^nd 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 < 10⁷ using the capped weight method.

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

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 < 10⁴ 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 < 10⁵ is 1759.83.

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

k < 10⁴ : 3323.50

k < 10⁵ : 3299.98

k < 10⁶ : 3300.58

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

k < 10⁴ : 3872.94

k < 10⁵ : 3858.37

k < 10⁶ : 3849.80

k < 10⁷ : 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 < 10⁴ : 4446.50

k < 10⁵ : 4282.14

k < 10⁶ : 4244.89

k < 10⁷ : 4236.23

k < 10⁸ : 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:

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:

and the averages are:

k < 10⁵ : 4454.00

k < 10⁶ : 4690.15

k < 10⁷ : 4602.97

k < 10⁸ : 4590.51

k < 10⁹ : 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 < 10⁹ with this condition are as follows:

and the averages are:

k < 10⁵ : 4348.33

k < 10⁶ : 4605.61

k < 10⁷ : 4582.50

k < 10⁸ : 4586.43

k < 10⁹ : 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 10⁹ and the following obtained:

and the averages are:

k < 10⁵ : 4775.00

k < 10⁶ : 4488.73

k < 10⁷ : 4580.71

k < 10⁸ : 4585.97

k < 10⁹ : 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 :

and the averages are:

k < 10⁵ : 4490.00

k < 10⁶ : 4611.55

k < 10⁷ : 4598.10

k < 10⁸ : 4589.92

k < 10⁹ : 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 :

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

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 :

The combined negative top 10 is :

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

The positive and negative modified Nash weights were calculated for all odd k < 10⁵. 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 10⁶. 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 10⁹, 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