Section 6 -
Numbers of the form k*2^{n} ± 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^{n} (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^{n} ± 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^{n} +1 is prime, there is a 1/k likelihood that k*2^{n} +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^{n} +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^{n} +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^{n} +1. Then n = qe + r + s for some q and s, chosen
so that 0 < s < e. Then k.2^{n} + 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^{n} +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^{n}
+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^{n} +1 is composite for all n ³ 1. Similarly, a **Riesel Number** is a
value k, k odd, such that k*2^{n} -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^{n} +1 is a prime,
and for all 1 £ m < n, k*2^{m}
+1 is composite, then k*2^{n} + 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^{n}
+1, then p also divides (k+2p)*2^{n} +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^{n}
+1 and k > 2p then p divides (k-2p)*2^{n}
+1. Repeating if necessary, we can see that p divides k'*2^{n} +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^{n} +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^{64} -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^{n} -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^{n} -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^{n} +1 and k.2^{n} -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^{n} +1
then p divides (2p-k).2^{n} -1.

Proof : Since k.2^{n} º -1
(mod p), we have (k-2p).2^{n} º -1
(mod p). Multiplying both sides by -1,
we obtain (2p-k).2^{n} º 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^{n}
+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^{n} -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^{n} -1 and k.2^{n} +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^{n}
-1, and chains of the second amongst
those numbers of the form k.2^{n} +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^{n} ±1
and k*2^{n+1} ±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 :

- Find the longest possible chains.
- 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^{n} ±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.