Keller Primes - The Search Extended

The most convenient way of searching for large prime numbers is to consider the form p = k*2n +1 where k is odd and n ³ 1. Every odd prime can be represented in this form, usually with low values of n and high values of k. When k is small, there are well-known primality tests for p available, based on the factorisation of p- 1, in this case readily obtainable, and for which many practical computer implementations exist.

For most values of k, there will be at least one small value of n (n < 30 say) for which k*2n +1 is prime, but this is not always the case. For convenience, let us say that k is an m-survivor if and only if there are no primes of the form k*2n +1 for any n £ m. Furthermore, k*2m +1 is a known as a Keller prime if k is an (m- 1)-survivor but not an m-survivor, that is, a Keller prime is the smallest prime of the form k*2m +1 for a fixed value of k. Alternatively, a Keller prime is the first occurrence of a prime in the sequence {k*2n +1, n = 1, 2, …}. As m increases, the frequency of m-survivors decreases as more and more Keller primes are found.

The divisibility properties of k with respect to the sequence {k*2n +1} have a profound bearing on the number of potential values that survive initial sieves by small primes. Elsewhere, it is proved that if r exists such that a prime p divides k*2r +1, then p divides k*2n +1 if and only if n º r (mod e) where e is the order of p to the base 2. Moreover, this r is unique (mod e). The pairs (p, r) are called Nash congruences. Primes of order e consist of all prime divisors of 2e - 1 which do not divides 2f - 1 where f < e. The set of all Nash congruences up to a specific maximum exponent e is known as a Nash sieve. Note that throughout, k is a fixed value.

Without trial division, we have created a densest possible sieve (subject to one or two conditions). If we apply the Nash sieve over a fixed range of exponents then the count of exponents not covered is called the Nash weight, which is a measure of the susceptibility of k to trial sieving.

From the basic theory, it can be demonstrated that there exist k such that every value in the sequence {k*2n +1} is divisible by at least one of a covering set of primes, that is, no Keller prime exists. These values of k are known as Sierpinski numbers. Sierpinski numbers are m-survivors for all m.

The smallest known Sierpinski number is k0 = 78557, and this in fact is believed to be the smallest. However, there are currently 11 values of k < 78557 for which no Keller prime is known. There are two major coordinated searches underway at present to locate Keller primes for these, pushing search ranges to very high values of n.

I have previously considered the range 78557 < k < 105 and extended this upper limit to 106. In this article I will outline the further extension to 107.

The basic approach is to maintain a list of k values which are n-survivors, while pushing the value of n continually higher. The list initially consists of every odd value of k in the range. For low values of n, I use straightforward trial division to establish whether k*2n +1 is prime or not. Those values that provide primes are discarded and all others preserved. When trial division becomes unreasonable except as an initial sieve, for n > 10 say, I move on to the (p- 1)-primality test. At this point, the primeform software pfgw is the most convenient tool. Eventually, with the length of the survivor list becoming substantially smaller, and the exponents reasonably large, say over 300, it is more convenient to cover ranges of exponents at a time. For n up to 2000, it is most convenient to use my own routines using Ultrabasic, where I can use a built-in break if a Keller prime is found. Beyond this point, the optimised code of primeform and proth are preferred, even though there is a small percentage of unnecessary overhead involved without the automatic halt once a prime is found.

Covering larger ranges at a time, the process becomes 4-fold. First, I use my own routines to generate a lightly pre-sieved list of possible primes. Then I use proth as a more substantial sieve, using a manual sieve limit higher than the automatic limit. The survivors are passed to pfgw, first using the probable prime test only. Numbers that pass this stage are then subjected to a full primality test, again using pfgw. The list of primes so obtained is used to shorten the survivor list.

In addition to extending the range of the search, I have turned to the negative case and given it an identical and parallel treatment. Simply put, this means considering the form k*2n - 1, which has equivalent negative versions of Nash congruences and Keller numbers. Negative Sierpinski numbers are known as Riesel numbers. The process of creating and maintaining the survivor list is very similar to the positive case, the only difference being the removal of my own routines from use except to perform the stage one sieve, since the (p+1)-primality test is complicated and already provided efficiently within pfgw.

For n £ 1000, complete set of statistics of the numbers of survivors at each exponent value for both the positive and negative cases are available as spreadsheets. For n in excess of 1000, the numbers of Keller primes found at each exponent is very low, and it is more useful and meaningful to preserve a list of the primes.

Survivor counts at various exponent values are provided in the following table. Bear in mind that at the start, the complete list contains 5*106 values.

 exponent positive survivors percentage negative survivors percentage percentage difference 1 4364564 87.29 4364830 87.30 - 0.00532 2 3807542 76.15 3807522 76.15 +0.00040 3 3363072 67.26 3363091 67.26 - 0.00038 4 2971601 59.43 2972702 59.45 - 0.02202 5 2675445 53.51 2676765 53.54 - 0.02640 6 2404196 48.08 2405279 48.11 - 0.02166 7 2189243 43.78 2189837 43.80 - 0.01188 8 1987415 39.75 1987029 39.74 +0.00772 9 1832786 36.66 1832589 36.65 +0.00394 10 1687099 33.74 1687067 33.74 +0.00064 20 918630 18.37 919838 18.40 - 0.02416 30 621053 12.42 621531 12.43 - 0.00956 40 466294 9.326 465966 9.319 +0.00656 50 375294 7.506 375036 7.501 +0.00516 60 312920 6.258 312610 6.252 +0.00620 70 270730 5.415 270997 5.420 - 0.00534 80 238883 4.778 239001 4.780 - 0.00236 90 214719 4.294 214602 4.292 +0.00234 100 194954 3.899 194829 3.897 +0.00250 200 106799 2.136 107112 2.142 - 0.00626 300 77410 1.548 77576 1.552 - 0.00332 400 62607 1.252 62649 1.253 - 0.00084 500 53330 1.067 53283 1.066 +0.00094 600 47038 0.9408 46981 0.9396 +0.00114 700 42543 0.8509 42389 0.8478 +0.00308 800 38949 0.7790 38904 0.7781 +0.00090 900 36097 0.7219 36108 0.7222 - 0.00022 1000 33813 0.67626 33803 0.67606 +0.00020 2000 22470 0.44940 22374 0.44748 +0.00192 3000 18076 0.36152 17971 0.35942 +0.00210 4000 15541 0.31082 15447 0.30894 +0.00188 5000 13909 0.27818 13800 0.27600 +0.00218 6000 12691 0.25382 12581 0.25162 +0.00220 7000 11749 0.23498 11700 0.23400 +0.00098 8000 11044 0.22088 10970 0.21940 +0.00148 9000 10479 0.20958 10359 0.20718 +0.00240 10000 10017 0.20034 9882 0.19764 +0.00270

Note that the positive survivor count includes 69 values of k identified as Sierpinski numbers, and the negative survivor count includes 65 values identified as Riesel numbers. One can see the very close correlation between the positive and negative counts, reflecting the duality of divisibility patterns.

Values of k which have high Nash weight will tend to require more testing than those with low Nash weight, since more exponents survive trial division. On the other hand, it is more likely that they will produce primes earlier in the search. The standard Nash weight is calculated over the k range 100001 to 110000, with an exponent limit of 256, and a Nash weight in excess of 1000 is considered to be particularly high. We would therefore expect the number of such k remaining in the survivor list to drop at a faster rate than the list length itself. The following table shows this explicitly, for the positive case only.

 search limit count of surviving high Nash weights 1000 362 2000 108 3000 57 4000 33 5000 20 6000 15 7000 13 8000 11 9000 9 10000 8

The percentage drop for all survivors between n = 1000 and n = 10000 is approximately 70%, whereas the equivalent drop for those of Nash weight ³ 1000 is almost 98%.

In the positive case, the first exponent value that does not provide any Keller primes is n = 2059. Thereafter, the number of such exponents increases in frequency. This sequence continues 2106, 2215, 2234, 2256, 2401, 2563, 2641, 2652, 2659, 2692, 2693, 2788, 2822, 2880, 2908, 2948, 2983, 3061, 3097, 3100, etc. The first occurrence of two consecutive exponents providing no Keller primes is 2692 & 2693. Analogously, the first run of three consecutive exponents providing no Keller prime is {4090, 4091, 4092}, the first run of four begins at 4152, five at 5087, six and seven at 6548, eight to thirteen at 7699, and fourteen at 9115.

Equivalently, in the negative case, the first exponent not providing any Keller primes is n = 2267, with the sequence continuing 2301, 2513, 2613, 2680, 2691, 2737, 2773, 2823, etc. The first occurrence of a pair of consecutive exponents giving no Keller primes is 2933 & 2934, the first run of three begins at 3580, four at 4854, five at 6497, six to eight at 6978, and nine to twelve at 8107.

The first dual occurrence of an exponent giving no positive or negative Keller primes is n = 3279, the first dual pair is at n = 4082, the first run of three begins at 5640, and four and five at 7401.

In the previous version of the positive side of this search, when exponent n = 10000 was reached, the survivors were passed out to interested collaborators to proceed further. Allocation of survivors was basically random, and the contributors were (and still are!) allowed to pursue individual searches as they saw fit, as long as they informed me of any primes discovered, and search limits otherwise. However, faster computers and the available software allow me to continue on my own much further. The following table gives the survivor statistics up to n = 20000.

 exponent positive survivors percentage negative survivors percentage 11000 9586 0.19172 9499 0.18998 12000 9226 0.18452 9135 0.18270 13000 8916 0.17832 8835 0.17670 14000 8634 0.17268 8545 0.17090 15000 8391 0.16782 8305 0.16610 16000 8150 0.16300 8064 0.16128 17000 7940 0.15880 7857 0.15714 18000 7738 0.15476 7669 0.15338 19000 7542 0.15084 7490 0.14980 20000 7400 0.14800 7301 0.14602

This process is continuing, so please contact me if you are interested in finding out the current search limits. Lists of 1000-survivors and Keller primes for both the positive and negative cases are also available.