Cunningham chain

In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes.

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = 2 p_i + 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₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = 2 p_i - 1.

Cunningham chains are also sometimes generalized to sequences of prime numbers (p₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = ap_i + b for fixed coprime integers 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.

According to the strong prime k-tuple conjecture, which is widely believed to be true, for every $k$ there are infinitely many Cunningham chains of length $k$. [1] There are, however, no known direct methods of generating such chains.

Largest known Cunningham chain of length k (as of August 2006)

k	Kind	p1 (starting prime)	Digits	Year	Discoverer
2	1st	137211941292195×2171960 − 1	51780	2006	Z. Járai, G. Farkas, T. Csajbok, J. Kasza, A. Járai
3	1st	164210699973×226326 − 1	7937	2006	M. Paridon
4	1st	119184698×5501# − 1	2354	2005	J. Sun
5	2nd	1719674368×1447# + 1	613	2004	D. Augustin
6	2nd	37783362904×1097# + 1	475	2006	D. Augustin
7	2nd	414792720846×557# + 1	237	2006	D. Augustin
8	1st	2×65728407627×431# − 1	186	2005	D. Augustin
9	1st	65728407627×431# − 1	185	2005	D. Augustin
10	2nd	145683282311×181# + 1	84	2005	D. Augustin
11	2nd	2×(8428860×127# + 212148902055091) − 1	56	2006	J. K. Andersen
12	2nd	8428860×127# + 212148902055091	56	2006	J. K. Andersen
13	1st	1753286498051×71# − 1	39	2005	D. Augustin
14	1st	9510321949318457733566099	25	2004	J. K. Andersen
15	1st	11993367147962683402919	23	2004	T. Alm, J. K. Andersen
16	1st	810433818265726529159	21	2002	P. Carmody, P. Jobling

q# denotes the primorial 2×3×5×7×...×q.

As of October 2006, 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:

Binary	Decimal
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

External links

• The Prime Glossary: Cunningham chain
• PrimeLinks++: Cunningham chain
• Cunningham Chain records
• Sequence A005602 in OEIS: the first term of the lowest complete Cunningham Chains of the first kind of length n, for 1 <= n <= 14
• Sequence A005603 in OEIS: the first term of the lowest complete Cunningham Chains of the second kind with length n, for 1 <= n <= 15