Cunningham chain
Encyclopedia : C : CU : CUN : Cunningham chain
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 [k] there are infinitely many Cunningham chains of length [k]. 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 [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]. Since each successive prime in the chain is [p_ = 2p_i + 1] it follows that [p_i \equiv 2^i - 1 \pmod]. Thus, [p_2 \equiv 3 \pmod], [p_3 \equiv 7 \pmod], 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_ = 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_]. 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_] is also 1. And, finally, we can see that [p_] 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 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 <= 15
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.