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.
One application for Cunningham chains is using computing power to identify them, in order to generate virtual currency, similar to how Bitcoin is mined.
Definition
A Cunningham chain of the first kind of length n is a sequence of prime numbers such that for all 1 ≤ i < n, pi+1 = 2pi + 1..It follows that
Or, by setting , we have
Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers such that for all 1 ≤ i < n, pi+1 = 2pi − 1.
It follows that the general term is
Now, by setting, we have.
Cunningham chains are also sometimes generalized to sequences of prime numbers 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 and the next terms in the chain are not prime numbers.
Examples
Examples of complete Cunningham chains of the first kind include these:Examples of complete Cunningham chains of the second kind include these:
Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem... can be implemented in any field where the discrete logarithm problem is difficult."
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.There are computing competitions for the longest Cunningham chain or for the one built up of the largest primes, but unlike the breakthrough of Ben J. Green and Terence Tao - the Green–Tao theorem, that there are arithmetic progressions of primes of arbitrary length - there is no general result known on large Cunningham chains to date.
| k | Kind | p1 | Digits | Year | Discoverer |
| 1 | 1st / 2nd | 277232917 − 1 | 23249425 | 2017 | Curtis Cooper, GIMPS |
| 2 | 1st | 2618163402417×21290000 − 1 | 388342 | 2016 | PrimeGrid |
| 2 | 2nd | 7775705415×2175115 + 1 | 52725 | 2017 | Serge Batalov |
| 3 | 1st | 1815615642825×244044 − 1 | 13271 | 2016 | Serge Batalov |
| 3 | 2nd | 742478255901×240067 + 1 | 12074 | 2016 | Michael Angel & Dirk Augustin |
| 4 | 1st | 13720852541*7877# − 1 | 3384 | 2016 | Michael Angel & Dirk Augustin |
| 4 | 2nd | 17285145467*6977# + 1 | 3005 | 2016 | Michael Angel & Dirk Augustin |
| 5 | 1st | 31017701152691334912*4091# − 1 | 1765 | 2016 | Andrey Balyakin |
| 5 | 2nd | 181439827616655015936*4673# + 1 | 2018 | 2016 | Andrey Balyakin |
| 6 | 1st | 2799873605326×2371# - 1 | 1016 | 2015 | Serge Batalov |
| 6 | 2nd | 52992297065385779421184*1531# + 1 | 668 | 2015 | Andrey Balyakin |
| 7 | 1st | 82466536397303904*1171# − 1 | 509 | 2016 | Andrey Balyakin |
| 7 | 2nd | 25802590081726373888*1033# + 1 | 453 | 2015 | Andrey Balyakin |
| 8 | 1st | 89628063633698570895360*593# − 1 | 265 | 2015 | Andrey Balyakin |
| 8 | 2nd | 2373007846680317952*761# + 1 | 337 | 2016 | Andrey Balyakin |
| 9 | 1st | 553374939996823808*593# − 1 | 260 | 2016 | Andrey Balyakin |
| 9 | 2nd | 173129832252242394185728*401# + 1 | 187 | 2015 | Andrey Balyakin |
| 10 | 1st | 3696772637099483023015936*311# − 1 | 150 | 2016 | Andrey Balyakin |
| 10 | 2nd | 2044300700000658875613184*311# + 1 | 150 | 2016 | Andrey Balyakin |
| 11 | 1st | 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 | 140 | 2013 | Primecoin |
| 11 | 2nd | 341841671431409652891648*311# + 1 | 149 | 2016 | Andrey Balyakin |
| 12 | 1st | 288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1 | 113 | 2014 | Primecoin |
| 12 | 2nd | 906644189971753846618980352*233# + 1 | 121 | 2015 | Andrey Balyakin |
| 13 | 1st | 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 | 107 | 2014 | Primecoin |
| 13 | 2nd | 38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1 | 101 | 2014 | Primecoin |
| 14 | 1st | 4631673892190914134588763508558377441004250662630975370524984655678678526944768*47# - 1 | 97 | 2018 | Primecoin |
| 14 | 2nd | 5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1 | 100 | 2014 | Primecoin |
| 15 | 1st | 14354792166345299956567113728*43# - 1 | 45 | 2016 | Andrey Balyakin |
| 15 | 2nd | 67040002730422542592*53# + 1 | 40 | 2016 | Andrey Balyakin |
| 16 | 1st | 91304653283578934559359 | 23 | 2008 | Jaroslaw Wroblewski |
| 16 | 2nd | 2×1540797425367761006138858881 − 1 | 28 | 2014 | Chermoni & Wroblewski |
| 17 | 1st | 2759832934171386593519 | 22 | 2008 | Jaroslaw Wroblewski |
| 17 | 2nd | 1540797425367761006138858881 | 28 | 2014 | Chermoni & Wroblewski |
| 18 | 2nd | 658189097608811942204322721 | 27 | 2014 | Chermoni & Wroblewski |
| 19 | 2nd | 79910197721667870187016101 | 26 | 2014 | Chermoni & Wroblewski |
q# denotes the primorial 2×3×5×7×...×q.
, the longest known Cunningham chain of either kind is of length 19, discovered by Jaroslaw Wroblewski in 2014.
Congruences of Cunningham chains
Let the odd prime be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus. Since each successive prime in the chain is it follows that. Thus,,, and so forth.The above property can be informally observed by considering the primes of a chain in base 2. When we consider in base 2, we see that, by multiplying by 2, the least significant digit of becomes the secondmost least significant digit of. Because is odd—that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of is also 1. And, finally, we can see that will be odd due to the addition of 1 to. 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 |
A similar result holds for Cunningham chains of the second kind. From the observation that and the relation it follows that. In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each, the number of zeros in the pattern for is one more than the number of zeros for. As with Cunningham chains of the first kind, the bits left of the pattern shift left by one position with each successive prime.
Similarly, because it follows that. But, by Fermat's little theorem,, so divides . Thus, no Cunningham chain can be of infinite length.