Cunningham chain

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 (p1,...,pn) such that for all 1 ≤ i < n, pi+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 p2 = 2p1 + 1, p3 = 4p1 + 3, p4 = 8p1 + 7, ..., pi = 2i − 1p1 + (2i − 1 − 1).

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

Cunningham chains are also sometimes generalized to sequences of prime numbers (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = api + 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.

[edit] Congruences of Cunningham chains of the first kind

Let the odd prime p1 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 pi + 1 = 2pi + 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 pi + 1 = 2pi + 1 in base 2, we see that, by multiplying pi by 2, the least significant digit of pi becomes the secondmost least significant digit of pi + 1. Because pi is odd--that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of pi + 1 is also 1. And, finally, we can see that pi + 1 will be odd due to the addition of 1 to 2pi. 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

[edit] External links

Retrieved from "http://en.wikipedia.org../../../c/u/n/Cunningham_chain.html"
In other languages