Cunningham chain
From Free net encyclopedia
In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham.
A Cunningham chain of the first kind 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). Similarly, a Cunningham chain of the second kind 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 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 <math>k</math> there are infinitely many Cunningham chains of length <math>k</math>. There are, however, no known direct methods of generating such chains.
As of August 2005, the longest Cunningham chain of either kind found 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 <math>p_1</math> be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus <math>p_1 \equiv 1 \pmod{2}</math>. Since each successive prime in the chain is <math>p_{i+1} = 2p_i + 1</math> it follows that <math>p_i \equiv 2^i - 1 \pmod{2^i}</math>. Thus, <math>p_2 \equiv 3 \pmod{4}</math>, <math>p_3 \equiv 7 \pmod{8}</math>, 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 <math>p_{i+1} = 2p_i + 1</math> in base 2, we see that, by multiplying <math>p_i</math> by 2, the least significant digit of <math>p_i</math> becomes the secondmost least significant digit of <math>p_{i+1}</math>. Because <math>p_i</math> is odd--that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of <math>p_{i+1}</math> is also 1. And, finally, we can see that <math>p_{i+1}</math> will be odd due to the addition of 1 to <math>2p_i</math>. 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 5 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 <= 15de:Cunningham-Kette