Cunningham Chain Article Index for
Cunningham 		Website Links For
Cunningham 		 

Information About

Cunningham Chain
  CATEGORIES ABOUT CUNNINGHAM CHAIN
   
prime numbers
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



A Cunningham chain of the first kind of length ''n'' is a sequence of prime numbers (''p''1,...,''pn'') such that for all 1 ≤ ''i'' < ''n'', ''p''''i''+1 = 2 ''pi'' + 1. (Hence each term of such a chain except the last one is a Sophie Germain Prime , and each term except the first is a Safe Prime ).

It follows that p_2 = 2p_1+1, p_3 = 4p_1+3, p_4 = 8p_1+7, ..., p_i = 2^{i-1}p_1 + (2^{i-1}-1) .

Similarly, a Cunningham chain of the second kind of length ''n'' is a sequence of prime numbers (''p''1,...,''pn'') such that for all 1 ≤ ''i'' < ''n'', ''p''''i''+1 = 2 ''pi'' - 1.

Cunningham chains are also sometimes generalized to sequences of prime numbers (''p''1,...,''pn'') such that for all 1 ≤ ''i'' < ''n'', ''p''''i''+1 = ''api'' + ''b'' for fixed Coprime Integer s ''a'', ''b''; the resulting chains are called generalized Cunningham chains.

A Cunningham chain is called complete if it cannot be further extended, i.e., if the previous or next term in the chain would not be a prime number anymore.


LARGEST KNOWN CUNNINGHAM CHAINS


It follows from Dickson's Conjecture and the broader Schinzel's Hypothesis H , both widely believed to be true, that for every k there are infinitely many Cunningham chains of length k. There are, however, no known direct methods of generating such chains.

''q''# denotes the Primorial 2×3×5×7×...×''q''.

As Of June 2007 , the longest known Cunningham chain of either kind is of length 16. Such a chain of the second kind was discovered by Tony Forbes in 1997, starting with 3203000719597029781. A chain of the first kind was discovered by Phil Carmody and Paul Jobling in 2002, starting with 810433818265726529159.


CONGRUENCES OF CUNNINGHAM CHAINS OF THE FIRST KIND


Let the odd prime p_1 be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus p_1 \equiv 1 \pmod{2}. Since each successive prime in the chain is p_{i+1} = 2p_i + 1 it follows that p_i \equiv 2^i - 1 \pmod{2^i}. Thus, p_2 \equiv 3 \pmod{4}, p_3 \equiv 7 \pmod{8}, and so forth.

The above property can be informally observed by considering the primes of a chain in base 2. (Note that, as with all bases, multiplying by the number of the base "shifts" the digits to the left.) When we consider p_{i+1} = 2p_i + 1 in base 2, we see that, by multiplying p_i by 2, the least significant digit of p_i becomes the secondmost least significant digit of p_{i+1}. Because p_i is odd--that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of p_{i+1} is also 1. And, finally, we can see that p_{i+1} will be odd due to the addition of 1 to 2p_i. In this way, successive primes in a Cunningham chain are essentially shifted left in binary with ones filling in the least significant digits. For example, here is a complete length 6 chain which starts at 141361469:


REFERENCES



EXTERNAL LINKS