Keller Primes - The Search Extended

The most convenient way of searching for large prime numbers is to consider the form p = k*2ⁿ +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*2ⁿ +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*2ⁿ +1 for any n £ m. Furthermore, k*2^m +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*2^m +1 for a fixed value of k. Alternatively, a Keller prime is the first occurrence of a prime in the sequence {k*2ⁿ +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*2ⁿ +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*2^r +1, then p divides k*2ⁿ +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 2^e - 1 which do not divides 2^f - 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*2ⁿ +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 k₀ = 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 < 10⁵ and extended this upper limit to 10⁶. In this article I will outline the further extension to 10⁷.

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*2ⁿ +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*2ⁿ - 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*10⁶ values.

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.

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.

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.