Section 6 - Numbers of the form k*2ⁿ ± 1

We have seen that numbers of this form appear as divisors of Generalised Fermat Numbers, and spring up elsewhere frequently, and we also have a convenient primality test in the positive case (i.e. when the sign is +) when k < 2ⁿ (which is the norm when we are looking for large primes) in terms of the Proth Test. In fact, the Proth Test is a pseudoprimality test in the negative case and can be used to rule out all but a very few values, which then have to be run through a full Lucasian test.

In fact, every number can be written in the form k*2ⁿ ± 1 for k odd by simply adding or subtracting 1 and then extracting every possible power of 2. This is therefore a very convenient form to consider, and is worthwhile investigating further. I shall often refer to numbers of this form as Robinson Numbers or Proth Numbers.

I shall in this section consider the value of k to be the dominant of the (k, n) pair. There are several reasons for this, not least the theory of Dubner and Keller that for a particular k, and n such that k*2ⁿ +1 is prime, there is a 1/k likelihood that k*2ⁿ +1 divides a Fermat Number.

For a particular value of k, we shall sieve over the exponent n. This means that we attempt to remove as many n as possible (in a given range) from consideration as primes by finding factors. In the following, k is always odd. We wish to develop some divisibility theory. Most of what follows will be presented in the positive case, but the negative case is closely analogous.

Lemma 6.1. For an odd prime p, if there exists r such that 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 base 2.

Proof : By Lemma 1.1, we know that there exists q such that n = qe + r. We then have k.2ⁿ +1 º k.2^qe+r +1 º k.(2^e)^q.2^r + 1 º k.2^r +1 º 0 (mod p), as required. On the contrary, suppose there exists n ¹ r (mod e) such that p divides k.2ⁿ +1. Then n = qe + r + s for some q and s, chosen so that 0 < s < e. Then k.2ⁿ + 1 º k.2^r.2^s + 1 º 0 (mod p). Since k.2^r º -1 (mod p), this implies that 2^s º 1 (mod p), contradicting the minimality of e. Hence result.

Lemma 6.2. For an odd prime p and odd k, if p does not divide k, then p divides k.2^r +1 if and only if 2^x + k º 0 (mod p) for some x such that r + x º 0 (mod e), where e is the order of p to base 2.

Proof : Suppose r exists. Choose q such that qe ³ r. We have k.2^r º -1 º -2^qe (mod p). We can divide by 2^r to obtain k º -2^qe-r (mod p). We can then take x = qe - r. In the opposite direction, suppose 2^x + k º 0 (mod p). Then k º -2^x (mod p). Let r = qe-x for some q. We multiply both sides by 2^-x to obtain k.2^-x º -1 (mod p). Since 2^qe º 1 (mod p), we can insert 2^qe and add 1 to either side to obtain k.2^qe-x + 1 º 0 (mod p), that is, k.2^r + 1 º 0 (mod p). Hence result.

Lemma 6.3. In Lemma 6.2, if r exists, it is unique (mod e).

Proof : Suppose not. Then p divides both k.2^r +1 and k.2^s +1 for 0 £ r, s < e. Suppose s > r and let t = s-r. Then 0 º 2^t.(k.2^r +1) - (k.2^s +1) º (2^t -1) (mod p), that is, 2^t º 1 (mod p), which contradicts the minimality of e. Hence result.

Lemma 6.4. For an odd prime p, 2^f º 1 (mod p) if and only if f is a multiple of the order e of p to base 2. Thus 2^f - 1 factors into primes of exponent dividing f. This also means that the number of primes with a given exponent is finite.

Proof : Suppose 2^f º 1 (mod p) and let f = qe + r for some q and r, with 0 < r < e. Then 2^f º 2^qe+r º 2^r º 1 (mod p), which contradicts the minimality of e. Thus r = 0. The contrary is immediate from the definition of e. Hence result.

We are now in a position to introduce a very useful and important concept that can be used to replace trial division, especially over large ranges with the same k value.

Definition : The Nash Sieve is defined as follows. Let k be a fixed odd number. For each possible value of exponent e, up to a given limit, we identify the primes in the factorisation of 2^e -1 that do not occur in the factorisation of any smaller number of this form. The primes so obtained are (all) those with order e by Lemma 6.1. We then check this set of primes to see if they divide any one of the numbers 2^x + k for 0 £ x < e. If p divides 2^x + k, then by definition p does not divide k, and we also let r = -x (mod e). Then by Lemma 6.2, p divides k.2^r +1 and so divides k.2ⁿ +1 for any n of the form qe + r where q > 0. The list of Nash congruences k.2^r +1 º 0 (mod p) built up in this way, identified more simply by the pair (p, r), is the Nash sieve (to whatever limit is placed on e). Lemma 6.2 is used in an actual implementation so that for each p being considered, we can check whether p divides either 2^q + k or k.2^q +1 for q running from 0 to [e/2] and take r to be either - q (mod e) or q respectively. As soon as one or other of these divisions is true, the search for that p can be halted immediately by Lemma 6.3.

The Nash-Jobling implementation of the Nash sieve, called psieve, avoids the burden of having to factorize 2^e -1 by calculating the greatest common factor between 2^e -1 and 2^x + k for 0 £ x < e, and extracting any new primes that appear. This program has a large number of optional parameters, relating to subjects that we shall be introducing from now on.

Definition : For a given value of k, if (p, r) is a Nash congruence obtained in the above manner, then p covers the values of n = qe + r for any q, and, logically, n is said to be covered by p. Applying the Nash sieve to a fixed range of n to eliminate from consideration any value covered by (at least) one of the primes leaves a list of n which either have to be tested for primality directly or subjected to a larger sieve. The count of those n not covered after applying the Nash sieve is called the Nash weight. The standard Nash weight is calculated over the range 100000 £ n < 110000 and a limit on the exponent e of 256.

The more Nash congruences that we provide for k, the more values of n that can be covered. Is it too much to hope that we can produce a Nash sieve that covers every single possible n ? In general, the answer is no, since it is easy to find lots of primes of the form k*2ⁿ +1. However, there are certain cases when the answer is yes.

Definition. A Sierpinski Number is a value k, k odd, such that k*2ⁿ +1 is composite for all n ³ 1. Similarly, a Riesel Number is a value k, k odd, such that k*2ⁿ -1 is composite for all n ³ 1.

As long as the ranges we are working over are suitably large for both n and e, a zero Nash weight identifies a Sierpinski number. In this case, the primes in the Nash sieve comprise what is known as a covering set for k. Some of the primes may be redundant as they cover the same values of n, and so the idea of a covering set is usually modified to include the idea of minimality, that is, a covering set no subset of which is a covering set. The modulus of a covering set is the least common multiple of the exponents of the members of the set, and when referring in particular to Sierpinski numbers, is called the Sierpinski modulus. For a given k, if every exponent from 1 to m can be covered by primes of exponent dividing m, then it follows that k is a Sierpinski number with modulus at most m. Removing redundancy will produce the covering set. The smallest known Sierpinski number is 78557, which has covering set {3,5,7,13,19,37,73} and modulus 36. Any smaller Sierpinski number would have to have an enormous covering set and huge modulus, and, amongst those values of k less than 78557 for which no Robinson primes are known, this is unlikely.

If (p, r) is a Nash congruence, then we have k*2^r +1 º 0 (mod p). Subtracting 1 from either side and then dividing by 2^r we obtain the congruence k º -2^-r (mod p). If we have a set of Nash congruences, then we have a set of simultaneous congruences involving k, which we can always solve by the Chinese Remainder Theorem. Therefore, if we can obtain a set of primes and a set of Nash congruences that cover every possible position from 1 to the modulus (the lowest common multiple of the orders of the set of primes), then we can generate a Sierpinski number without ever having to search by brute force. I call the congruence k º - 2^-r (mod p) a Sierpinski congruence.

Definition. If k*2ⁿ +1 is a prime, and for all 1 £ m < n, k*2^m +1 is composite, then k*2ⁿ + 1 is known as a Keller Prime (for k).

Obviously, every odd k is either a Sierpinski number or has an associated Keller prime. In most cases, the Keller prime appears for some fairly small exponent n. However, there are values of k for which the Keller prime is very large. There are several different collaborative efforts underway to find the Keller primes for those k that do not appear to be Sierpinski (or Riesel) numbers, but have no Keller prime for small n. It is often, though not always, the case that such k have low Nash weights, i.e. there are lots of associated Nash congruences with small primes.

Values of low, but distinctly non-zero, (standard) Nash weight, typically less than 100, allow a search for Robinson primes to be pushed quickly to very high limits on n, with the hope of a very large prime being found. For extremely low scores, less than 30 say, it is possible that a small set of primes covers all but a few values of n, and that adding primes carefully to this set through some algorithm will eventually produce a covering set, possibly infinite. Another possibility is that there are values of k that satisfy the Sierpinski property for all but a finite set of exponents. These "almost Sierpinski" numbers are the subject of current research.

Logically, a quick way of ensuring a reasonably low Nash weight is to choose k that are not divisible by small primes, thereby increasing the likelihood of obtaining Nash congruences involving these primes. On the other hand, if k is divisible by a prime p, then Lemma 6.2 cannot be invoked, and there can be no Nash congruence for p. Hence if k is divisible by several small primes, it is more likely to have a high Nash weight.

Values of k with a high Nash weight (typically greater than 5000) are prized as they are potentially rich sources of very large Robinson primes. Such k occur infrequently (there are only six values of k < 10000 with Nash weight above 5000). However, by being selective, we can find or generate values of k which have Nash weight considerably higher still. For example, the value k = 302627325 has a Nash weight of 7093. For this value of k, the smallest prime providing a Nash congruence is 19.

We now look at how specific divisibility properties can be shared between related values of k by using simple modular arguments.

If p is a prime such that p divides k*2ⁿ +1, then p also divides (k+2p)*2ⁿ +1, obviously. Thus k+2p has the same divisibility properties as k with respect to p. Another way of viewing this is that k and k+2p have the same Nash congruence with respect to p. The idea extends to sets of primes. Thus, if P is a set of primes, and P also represents the product of the set, then k+2P has the same divisibility properties as k with respect to the set of primes. Similarly, if p divides k*2ⁿ +1 and k > 2p then p divides (k-2p)*2ⁿ +1. Repeating if necessary, we can see that p divides k'*2ⁿ +1 where k' = k (mod 2p). This also holds for set of primes, that is, if P is as before, then k (mod 2P) has the same divisibility properties as k with respect to P.

The next transformation is of particular importance.

Definition. If p divides k*2ⁿ +1, then p divides (2k+p)*2^n-1 +1, shifting the divisibility properties of k with respect to p by one exponent. Thus if k has a Nash congruence (p, r), then 2k+p has Nash congruence (p, r-1). This also extends to sets of prime P, so that replacing k by 2k+P affects each of the Nash congruences associated with the members if P in the same way. As with other iterations, we can apply the reduction argument to this non-trivially to obtain the Keller Iteration k ® (2k+P) mod 2P.

If k is a Sierpinski number and P is the product of the primes in the covering set for k, then all the numbers generated by the Keller iteration are also Sierpinski numbers with the same covering set. This iterative process repeats with period equal to the Sierpinski modulus m, since at this point all the Nash congruences re-align. The sequence of repeated numbers so generated is called a Keller cycle. The simpler iteration k ® (k+2P) provides an infinite sequence of Sierpinski numbers. Applying the Keller iteration to any one of these values will re-create the same Keller cycle. For every Sierpinski number k with covering set P such that k > 2P, there is then a base value k' = k (mod 2P), such that k' < 2P, and k' appears in a Keller cycle. Thus there is a finite number of base values, and therefore also of Keller cycles, for each finite covering set.

Note that it is entirely possible for a Sierpinski number to have two distinct covering sets, though usually there is heavy overlap in terms of individual primes. This happens when the Nash congruences of different sets of primes cover the same set of exponents. The smallest Sierpinski number with this property is 12151397, which has two covering sets {3, 5, 7, 13, 19, 73, 37} and {3, 5, 7, 13, 19, 73, 109}, both of modulus 36. In this case, 37 and 109 cover the same exponents and so are interchangeable. More complicated overlaps, involving sets of primes rather than individual values, do exist.

If the divisibility pattern of a covering set is laid out from 1 to m where m is the modulus, then the Keller iteration can be viewed as a shift in this pattern to the left by one position, and the m-th step re-aligns all the congruences and we arrive back at k. Thus we have the Keller cycle relating m different Sierpinski numbers. However, rather than simply shifting the congruences by 1, we may consider flipping the congruences about the midpoint m/2. In this case, the Nash congruence (p, r) becomes (p, m+1-r), associated with a mirror-image or flip Sierpinski number k'. Repeating this flip returns the original values. We have k.2^r +1 º 0 (mod p), and so k º -2^r (mod p). Replacing the exponent by m+1-r, we have k' º -2^r-1 (mod p). We then have a set of simultaneous congruences that can be solved to obtain k' < 2P, k odd, which always exists by the Chinese Remainder Theorem. We can then generate a flip cycle using the Keller iteration. This idea backs up the following.

Lemma 6.5. The number of distinct Keller cycles for each covering set is even unless every prime in the covering set has odd order modulo 2, or every prime in the covering set has even order modulo 2.

Proof : Since each Keller cycle has a flip cycle, it is enough to consider the case that a Keller cycle flips to itself. Suppose this is the case, and let p be a member of the covering set such that p has largest exponent e. The Nash congruence (p, r) flips to (p, r+x) for some offset x by definition. Therefore, we require m+1-r º r-x (mod e), that is, 2r º 1-x (mod e). Since there must be other Nash congruences covering all positions from 1 to m, there must be another prime, q say, q ¹ p, such that q covers position r+1. By symmetry, the congruence (q, r+1) flips to (q, r+x-1). Hence m+1-(r+1) º r+x-1 (mod e), that is 2r º 1-x (mod e). In general, each prime p_i ¹ p in the covering set covers position r+y_i for some value y_i, and we find that 2r º 1-x (mod e_i) for all i. Now, using the Keller iteration, we can suppose that r = m, since otherwise we can find another member of the Keller cycle for which this is the case. Thus we have x º 1 (mod e_i) for all i. Now, if e_i is even, x must be odd, and vice-versa, and hence the e_i are either all odd or all even, as required. Additionally, if there is a prime whose exponent is m, we must have x = 1 since by definition we have x < m.

Suppose the e_i are all even. Then they must all be powers of 2 since otherwise we could replace primes of order e_i with primes of odd exponent f_i such that f_i divides e_i. Consider modulus m = 64. There is only one covering set, consisting of all the primes dividing 2⁶⁴ -1, and one self-flipping Keller cycle, whose smallest value is 15511380746462593381.

As I implied earlier, Lemmas 6.2 and 6.3 have analogues for numbers of the form k.2ⁿ -1. Thus, for an odd prime p and odd number k, if there exists r such that p divides k.2^r -1, then p divides k.2ⁿ -1 if and only if n º r (mod e), where e is the exponent of p to base 2, and if p does not divide k, then p divides k.2^r -1 if and only if 2^x -k º 0 (mod p) for some x such that r + x º 0 (mod e). Hence we can build up Nash congruences, apply the Nash sieve and obtain Nash weights exactly as before. In order to differentiate, we shall refer to Nash weights associated with k.2ⁿ +1 and k.2ⁿ -1 as positive and negative Nash weights respectively. The connection between zero negative Nash weight and the Riesel property is taken as obvious. If (p, r) is a negative Nash congruence, then the corresponding congruence k º 2^-r (mod p) is called the Riesel congruence.

As an additional correspondence between signs, we have the following.

Lemma 6.6. If p divides k.2ⁿ +1 then p divides (2p-k).2ⁿ -1.

Proof : Since k.2ⁿ º -1 (mod p), we have (k-2p).2ⁿ º -1 (mod p). Multiplying both sides by -1, we obtain (2p-k).2ⁿ º 1 (mod p). Hence result.

It is obvious that the reverse is also true. The result is also true if p is replaced by a set of primes P. The result is also true if 2P > k, in which case we just take 2P-k (mod 2P) instead.

As the above implies, if P is a set of primes that produce Nash congruences with respect to numbers of the form k*2ⁿ +1 for some odd k, then k' = 2P-k (mod 2P if k > 2P) has the same Nash congruences with respect to numbers of the form k*2ⁿ -1. In particular, k and k' have the same Nash weight, that is, k has the same positive Nash weight as k' has negative Nash weight. This is true when k is a Sierpinski number with P as its covering set. In this case, k' is a Riesel number. Thus there is a direct correlation between Sierpinski and Riesel numbers and so only the positive half need be studied closely.

Rather than generate and apply Nash congruences in the manner associated with the Nash sieve, an alternative is to proceed sequentially through all primes up to a chosen limit. We then need to calculate the order of each prime modulo 2. However, this calculation throws out the value x defined by Lemma 6.2 as a by-product. The choice of primes may also be restricted by placing a limit on e to speed up the algorithm. For example, we may choose to consider all primes less than 2^r, but place a limit on e of 2^s for s £ r. Weights can be calculated using this sieve in exactly the same way as before. Overhead may be reduced by having a prepared list of primes and their exponents, in which case only the x values need to be calculated. This approach is even closer to trial division than the normal Nash sieve, and has practical use in finding numbers of very high Nash weight.

The Nash sieve can be modified to narrow the search for twin primes of the form k.2ⁿ -1 and k.2ⁿ +1. Basically, both a positive and a negative sieve are applied to the value of k and a Nash weight obtained by counting the number of exponents not covered by either sieve. The larger this weight, the more likely that twin primes will occur. The program psieve has an option to calculate this dual weight.

Definition. A Brier Number is a number that is simultaneously a Sierpinski number and a Riesel number.

In trying to locate Brier numbers, we require to find two separate covering sets P and Q such that for any prime p Î P Ç Q, the Sierpinski congruence and the Riesel congruence coincide. If this is the case, a different Brier number may be obtained from every different combination of covering patterns that exists. It is appropriate to obtain firstly a set of Nash congruences for k as a Sierpinski number, convert these to Sierpinski congruences, and for each overlapping prime, consider the Sierpinski congruence as a Riesel congruence and produce the associated Nash congruence. Once these are in place, we can then locate the remaining Nash congruences for k as a Riesel number.

Fortunately, the prime 3 can be used in both sets, eliminating even values of n in one case and odd values in the other one, otherwise the sizes of solutions would be huge. So let us suppose that 3 is in both sets. What other restrictions can be placed on overlapping primes ?

Lemma 6.7. Given the above definitions, suppose that 3 Î P Ç Q and suppose p Î P Ç Q, where p ¹ 3. Let e be the order of p modulo 2. Then e is twice an odd number.

Proof : Given a prime p, with order e modulo 2, we require the positive Nash congruence with respect to p to convert to a Sierpinski congruence that then converts back to a negative Nash congruence with respect to Q, and such that the two Nash congruences switch signs, otherwise p will have no effect since one or other of P and Q has prime 3 with matching sign. Thus the congruence chain from r (mod e) to -2^r (mod p) to 2^s (mod p) to s (mod e) must be such that r ¹ s (mod 2) and such that -2^r º 2^s (mod p). Since r-s is odd and 2^r-s º -1 (mod p), we have e = 2(r-s), and so the order of p must be twice an odd number.

This substantially restricts the available primes. In particular, 5 and 7 are excluded and so can occur in one or other of P and Q, but not both. Primes that can overlap include 11 and 19. The first Brier numbers found were obtained from two covering sets of orders 96 and 288, the smallest solution being of 41 digits. The smallest known at present is of 27 digits, obtained from covering sets of modulus 144 and 120.

Definition. A Cunningham chain of the first kind is a sequence of the form p, 2p+1, 4p+1, etc. and a Cunningham chain of the second kind is a sequence of the form p, 2p-1, 4p-1, etc.

The first prime in a Cunningham chain of the first kind of length 2 is just a Sophie-Germain prime. A Cunningham chain of the second kind of length 2 is sometimes known as a Cunningham pair. Chains of the first kind appear naturally amongst those numbers of the form k.2ⁿ -1, and chains of the second amongst those numbers of the form k.2ⁿ +1. The longer the length of a chain, the greater the restriction on the form of k. For instance, chains of length 2 require k º 3 (mod 6) and chains of length 4 require k º 15 (mod 30). A Nash weight may be calculated for a particular length m by counting the number of distinct sequences of exponents of length at least m remaining after applying a Nash sieve. A slightly different weight may be obtained by removing the word "distinct" in the preceding sentence.

Definition. A Bi-Twin is a set of 4 primes of the form k*2ⁿ ±1 and k*2ⁿ⁺¹ ±1. Here we have two sets of twin primes, a Cunningham chain of the first kind and a Cunningham chain of the second kind. We may extend this by defining a Bi-Chain to be simultaneous Cunningham chains of the first and second kinds with the same k values and n ranges. The smallest Bi-Twin (Bi-Chain of length 2) is the set {5,7,11,13}, where k = 3 and n = 1 & 2. The concepts of bi-twins and bi-chains were introduced by Henri Lifchitz, who maintains a website dedicated to them.

As with twin primes, the Nash sieve can be modified to narrow the search for Cunningham chains and bi-chains of length n by looking for n consecutive uncovered exponents in the positive and negative sieves. Obviously, as n increases, we are forcing tougher and tougher restrictions, and so we can search across larger ranges.

For Cunningham chains (CC) and bi-chains, there are two standard aims :

1. Find the longest possible chains.
2. For a specific length, find the largest possible chains.

Long chains are usually looked for amongst values with large k divisible by several small primes, and small n. The longest CC of the first kind currently known has length 14, with k = 12060367351573305765 and n = 5 (Forbes, 1997), and the longest CC of the second kind currently known has length 16, with k = 800750179899257445 and n = 2 (Forbes, 1997). It is now quite common to consider k explicitly of the form m*p# for some integer m and prime p, which fulfils the basic requirement on k.

The largest known Cunningham pairs and bi-twins can be found in the records section.

Records for longer chains can also be found in the records section.

The principal website dedicated to numbers of the form k*2ⁿ ±1 is maintained by Ray Ballinger and Wilfrid Keller, and covers finding large primes that might be divisors of Fermat Numbers and finding Keller primes for particular values of k. Gallot's proth is the program recommended on this site for conducting searches. However, more recently, several other useful pieces of software have become available. These include the sieve program Newpgen from Paul Jobling, the prp program from George Woltman, and pfgw from the openpfgw (primeform gallot woltman) group started by Chris Nash and principally maintained by Jim Fougeron.

For additional investigations into k values with low Nash weight, high Nash weight, Keller primes and Sierpinski numbers, may I suggest elsewhere on this website, starting at my introductory page.