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.

## Contents

* 1 Definition
* 2 Examples
* 3 Largest known Cunningham chains
* 4 Congruences of Cunningham chains
* 5 See also
* 6 References
* 7 External links

## Definition

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p1, ..., pn) such that pi+1 = 2pi + 1 for all 1 ≤ i < n. (Hence each term of such a chain except the last 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),

or, by setting a=p1+12 (the number a is not part of the sequence and need not be a prime number), we have pi=2ia−1.

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

It follows that the general term is

pi=2i−1p1−(2i−1−1).

Now, by setting a=p1−12, we have pi=2ia+1.

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

2, 5, 11, 23, 47 (The next number would be 95, but that is not prime.)
3, 7 (The next number would be 15, but that is not prime.)
29, 59 (The next number would be 119 = 7×17, but that is not prime.)
41, 83, 167 (The next number would be 335, but that is not prime.)
89, 179, 359, 719, 1439, 2879 (The next number would be 5759 = 13×443, but that is not prime.)

Examples of complete Cunningham chains of the second kind include these:

2, 3, 5 (The next number would be 9, but that is not prime.)
7, 13 (The next number would be 25, but that is not prime.)
19, 37, 73 (The next number would be 145, but that is not prime.)
31, 61 (The next number would be 121 = 112, but that is not prime.)

Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem ... [which] can be implemented in any field where the discrete logarithm problem is difficult."[1]

## 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.

Largest known Cunningham chain of length k (as of 17 March 2023[2])  k | Kind | p1 (starting prime) | Digits | Year | Discoverer

|
|
|
|
|

1 | 1st / 2nd | 282589933 − 1 | 24862048 | 2018 | Patrick Laroche, GIMPS
2 | 1st | 2618163402417×21290000 − 1 | 388342 | 2016 | PrimeGrid
2nd | 213778324725×2561417 \+ 1 | 169015 | 2023 | Ryan Propper & Serge Batalov
3 | 1st | 1128330746865×266439 − 1 | 20013 | 2020 | Michael Paridon
2nd | 742478255901×240067 \+ 1 | 12074 | 2016 | Michael Angel & Dirk Augustin
4 | 1st | 13720852541×7877# − 1 | 3384 | 2016 | Michael Angel & Dirk Augustin
2nd | 49325406476×9811# + 1 | 4234 | 2019 | Oscar Östlin
5 | 1st | 31017701152691334912×4091# − 1 | 1765 | 2016 | Andrey Balyakin
2nd | 181439827616655015936×4673# + 1 | 2018 | 2016 | Andrey Balyakin
6 | 1st | 2799873605326×2371# - 1 | 1016 | 2015 | Serge Batalov
2nd | 52992297065385779421184×1531# + 1 | 668 | 2015 | Andrey Balyakin
7 | 1st | 82466536397303904×1171# − 1 | 509 | 2016 | Andrey Balyakin
2nd | 25802590081726373888×1033# + 1 | 453 | 2015 | Andrey Balyakin
8 | 1st | 89628063633698570895360×593# − 1 | 265 | 2015 | Andrey Balyakin
2nd | 2373007846680317952×761# + 1 | 337 | 2016 | Andrey Balyakin
9 | 1st | 553374939996823808×593# − 1 | 260 | 2016 | Andrey Balyakin
2nd | 173129832252242394185728×401# + 1 | 187 | 2015 | Andrey Balyakin
10 | 1st | 3696772637099483023015936×311# − 1 | 150 | 2016 | Andrey Balyakin
2nd | 2044300700000658875613184×311# + 1 | 150 | 2016 | Andrey Balyakin
11 | 1st | 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 | 140 | 2013 | Primecoin (block 95569)
2nd | 341841671431409652891648×311# + 1 | 149 | 2016 | Andrey Balyakin
12 | 1st | 288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1 | 113 | 2014 | Primecoin (block 558800)
2nd | 906644189971753846618980352×233# + 1 | 121 | 2015 | Andrey Balyakin
13 | 1st | 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 | 107 | 2014 | Primecoin (block 368051)
2nd | 38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1 | 101 | 2014 | Primecoin (block 539977)
14 | 1st | 4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1 | 97 | 2018 | Primecoin (block 2659167)
2nd | 5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1 | 100 | 2014 | Primecoin (block 547276)
15 | 1st | 14354792166345299956567113728×43# - 1 | 45 | 2016 | Andrey Balyakin
2nd | 67040002730422542592×53# + 1 | 40 | 2016 | Andrey Balyakin
16 | 1st | 91304653283578934559359 | 23 | 2008 | Jaroslaw Wroblewski
2nd | 2×1540797425367761006138858881 − 1 | 28 | 2014 | Chermoni & Wroblewski
17 | 1st | 2759832934171386593519 | 22 | 2008 | Jaroslaw Wroblewski
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.

As of 2018[update], the longest known Cunningham chain of either kind is of length 19, discovered by Jaroslaw Wroblewski in 2014.[2]

## Congruences of Cunningham chains

Let the odd prime p1 be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus p1≡1(mod2). Since each successive prime in the chain is pi+1=2pi+1 it follows that pi≡2i−1(mod2i). Thus, p2≡3(mod4), p3≡7(mod8), 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 base "shifts" the digits to the left; e.g. in decimal we have 314 × 10 = 3140.) 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

A similar result holds for Cunningham chains of the second kind. From the observation that p1≡1(mod2) and the relation pi+1=2pi−1 it follows that pi≡1(mod2i). In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each i, the number of zeros in the pattern for pi+1 is one more than the number of zeros for pi. 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 pi=2i−1p1+(2i−1−1) it follows that pi≡2i−1−1(modp1). But, by Fermat's little theorem, 2p1−1≡1(modp1), so p1 divides pp1 (i.e. with i=p1). Thus, no Cunningham chain can be of infinite length.[3]

## See also

* Primecoin, which uses Cunningham chains as a proof-of-work system
* Bi-twin chain
* Primes in arithmetic progression

## References

1. ↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
2. ↑ 2.0 2.1 Norman Luhn & Dirk Augustin, Cunningham Chain records. Retrieved on 2018-06-08.
3. ↑ Löh, Günter (October 1989). "Long chains of nearly doubled primes". Mathematics of Computation 53 (188): 751–759. doi:10.1090/S0025-5718-1989-0979939-8. https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/.

## External links

* The Prime Glossary: Cunningham chain
* Primecoin discoveries (primes.zone): online database of primecoin findings with list of records and visualization
* PrimeLinks++: Cunningham chain
* OEIS sequence A005602 (Smallest prime beginning a complete Cunningham chain of length n (of the first kind)) \-- the first term of the lowest complete Cunningham chains of the first kind of length n, for 1 ≤ n ≤ 14
* OEIS sequence A005603 (Chains of length n of nearly doubled primes) \-- the first term of the lowest complete Cunningham chains of the second kind with length n, for 1 ≤ n ≤ 15

* v
* t
* e

Prime number classes

By formula|

* Fermat (22n \+ 1)
* Mersenne (2p − 1)
* Double Mersenne (22p−1 − 1)
* Wagstaff (2p \+ 1)/3
* Proth (k·2n \+ 1)
* Factorial (n! ± 1)
* Primorial (pn# ± 1)
* Euclid (pn# + 1)
* Pythagorean (4n \+ 1)
* Pierpont (2m·3n \+ 1)
* Quartan (x4 \+ y4)
* Solinas (2m ± 2n ± 1)
* Cullen (n·2n \+ 1)
* Woodall (n·2n − 1)
* Cuban (x3 − y3)/(x − y)
* Carol (2n − 1)2 − 2
* Kynea (2n \+ 1)2 − 2
* Leyland (xy \+ yx)
* Thabit (3·2n − 1)
* Williams ((b−1)·bn − 1)
* Mills (⌊A3n⌋)

By integer sequence|

* Fibonacci
* Lucas
* Pell
* Newman–Shanks–Williams
* Perrin
* Partitions
* Bell
* Motzkin

By property|

* Wieferich (pair)
* Wall–Sun–Sun
* Wolstenholme
* Wilson
* Lucky
* Fortunate
* Ramanujan
* Pillai
* Regular
* Strong
* Stern
* Supersingular (elliptic curve)
* Supersingular (moonshine theory)
* Good
* Super
* Higgs
* Highly cototient

Base-dependent|

* Happy
* Dihedral
* Palindromic
* Emirp
* Repunit (10n − 1)/9
* Permutable
* Circular
* Truncatable
* Strobogrammatic
* Minimal
* Weakly
* Full reptend
* Unique
* Primeval
* Self
* Smarandache–Wellin
* Tetradic

Patterns|

* Twin (p, p \+ 2)
* Bi-twin chain (n − 1, n \+ 1, 2n − 1, 2n \+ 1, …)
* Triplet (p, p \+ 2 or p \+ 4, p \+ 6)
* Quadruplet (p, p \+ 2, p \+ 6, p \+ 8)
* k−Tuple
* Cousin (p, p \+ 4)
* Sexy (p, p \+ 6)
* Chen
* Sophie Germain (p, 2p + 1)
* Cunningham (p, 2p ± 1, 4p ± 3, 8p ± 7, ...)
* Safe (p, (p − 1)/2)
* Arithmetic progression (p \+ a·n, n = 0, 1, 2, 3, ...)
* Balanced (consecutive p − n, p, p \+ n)

By size|

* Titanic (1,000+ digits)
* Gigantic (10,000+ digits)
* Mega (1,000,000+ digits)
* Largest known

Complex numbers|

* Eisenstein prime
* Gaussian prime

Composite numbers|

* Pseudoprime
* Catalan
* Elliptic
* Euler
* Euler–Jacobi
* Fermat
* Frobenius
* Lucas
* Somer–Lucas
* Strong
* Carmichael number
* Almost prime
* Semiprime
* Interprime
* Pernicious

Related topics|

* Probable prime
* Industrial-grade prime
* Illegal prime
* Formula for primes
* Prime gap

First 60 primes|

* 2
* 3
* 5
* 7
* 11
* 13
* 17
* 19
* 23
* 29
* 31
* 37
* 41
* 43
* 47
* 53
* 59
* 61
* 67
* 71
* 73
* 79
* 83
* 89
* 97
* 101
* 103
* 107
* 109
* 113
* 127
* 131
* 137
* 139
* 149
* 151
* 157
* 163
* 167
* 173
* 179
* 181
* 191
* 193
* 197
* 199
* 211
* 223
* 227
* 229
* 233
* 239
* 241
* 251
* 257
* 263
* 269
* 271
* 277
* 281

List of prime numbers

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Cunningham chain. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Cunningham_chain&oldid=213705"
*[OEIS]: On-Line Encyclopedia of Integer Sequences
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template