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.

Definition

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p₁, ..., p_n) such that for all 1 ≤ i < n, p_i+1 = 2p_i + 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

\begin{align} p_2 & = 2p_1+1, \\ p_3 & = 4p_1+3, \\ p_4 & = 8p_1+7, \\ & {}\ \vdots \\ p_i & = 2^{i-1}p_1 + (2^{i-1}-1). \end{align}

Or, by setting $a = \frac{p_1 + 1}{2}$ (the number $a$ is not part of the sequence and need not be a prime number), we have $p_i = 2^{i} a - 1$

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

It follows that the general term is

p_i = 2^{i-1}p_1 - (2^{i-1}-1) \,

Now, by setting $a = \frac{p_1 - 1}{2}$ , we have $p_i = 2^{i} a + 1$ .

Cunningham chains are also sometimes generalized to sequences of prime numbers (p₁, ..., p_n) such that for all 1 ≤ i ≤ n, p_i+1 = ap_i + 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:

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 = 11², but that is not prime.)

151, 301, 601, 1201 (The next number would be 2401 = 7⁴, 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. A relevant open problem, Rassias' conjecture can also be stated in terms of Cunningham chains, namely: there exist Cunningham chains with parameters $2a, -1$ for $a$ such that $2a-1=p$ is a prime number.

Largest known Cunningham chain of length k (as of 5 May 2013^[2])
k	Kind	p₁ (starting prime)	Digits	Year	Discoverer
1	1st / 2nd	2^74207281 − 1	22338618	2016	Curtis Cooper, GIMPS
2	1st	18543637900515×2⁶⁶⁶⁶⁶⁷ − 1	200701	2012	Philipp Bliedung, PrimeGrid
2	2nd	648309×2¹⁴⁸³¹⁰ + 1	44652	2010	Tom Wu
3	1st	5110664609396115×2³⁴⁹⁴⁴ − 1	10535	2014	Gevay, Vatai, Farkas & Jarai
3	2nd	82659189×2²⁶⁹⁹⁷ + 1	8135	2010	Tom Wu
4	1st	1249097877×6599# − 1	2835	2011	Michael Angel
4	2nd	630698711×4933# + 1	2105	2010	Michael Angel
5	1st	4250172704×2749# − 1	1183	2012	Dirk Augustin
5	2nd	80670856865×2677# + 1	1140	2011	Michael Angel
6	1st	2799873605326×2371# - 1	1016	2015	Serge Batalov
6	2nd	480112483568×1511# + 1	650	2014	Östlin
7	1st	162597166369×827# − 1	356	2010	Dirk Augustin
7	2nd	668302064×593# + 786153598231	251	2008	Thomas Wolter & Jens Kruse Andersen
8	1st	2×65728407627×431# − 1	186	2005	Dirk Augustin
8	2nd	1148424905221×509# + 1	224	2010	Dirk Augustin
9	1st	65728407627×431# − 1	185	2005	Dirk Augustin
9	2nd	182887101390961871050645934589918687746535370612015546956692154622371784133412186×223# + 1	167	2013	Primecoin (block 79349)
10	1st	44598464649019035883154084128331646888059795218766083584048621139159337786287845212160000×149# − 1	146	2013	Primecoin (block 182690)
10	2nd	61817679876032272550156670131676808699749929053121752139098662160409729216×179# + 1	145	2014	Primecoin (block 519253)
11	1st	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin (block 95569)
11	2nd	8026337833619599372491948674562462668692014872229571339857384053514279156849912832×109# + 1	127	2014	Primecoin (block 365304)
12	1st	61592551716229060392971860549140211602858978086524024531871935735163762961673908480×71# − 1	110	2013	Primecoin (block 239833)
12	2nd	160433998429454286861864982184342218645773889300991352796925862298096263175269000×73# + 1	109	2013	Primecoin (block 323183)
13	1st	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Primecoin (block 368051)
13	2nd	568980826640711977012761168233683848109012030650333480799148348813080407943543452×47# + 1	99	2014	Primecoin (block 519344)
14	1st	2×27353790674175627273118204975428644651729 + 1	41	2014	Jaroslaw Wroblewski
14	2nd	5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1	100	2014	Primecoin(block 547267)
15	1st	27353790674175627273118204975428644651729	41	2014	Jaroslaw Wroblewski
15	2nd	28320350134887132315879689643841	32	2008	Jaroslaw Wroblewski
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.

As of 2015, 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 $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{2}$ . Since each successive prime in the chain is $p_{i+1} = 2p_i + 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 $p_{i+1} = 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_{i+1}$ . 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_{i+1}$ is also 1. And, finally, we can see that $p_{i+1}$ 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 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 $p_1 \equiv 1 \pmod{2}$ and the relation $p_{i+1} = 2 p_i - 1$ it follows that $p_i \equiv 1 \pmod{2^i}$ . 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 $p_{i+1}$ is one more than the number of zeros for $p_i$ . 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 $p_i = 2^{i-1}p_1 + (2^{i-1}-1) \,$ it follows that $p_i \equiv 2^{i-1} - 1 \pmod{p_1}$ . But, by Fermat's little theorem, $2^{p_1-1} \equiv 1 \pmod{p_1}$ , so $p_1$ divides $p_{p_1}$ (i.e. with $i = p_1$ ). Thus, no Cunningham chain can be of infinite length.^[3]

References

↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
1 2 Dirk Augustin, Cunningham Chain records. Retrieved on 2014-05-05.
↑ 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.

External links

The Prime Glossary: Cunningham chain
PrimeLinks++: Cunningham chain
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

Prime number classes

By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Quartan (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))

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 (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin

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 chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)

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

Complex numbers	Eisenstein prime Gaussian prime

Composite numbers	Pseudoprime Almost prime Semiprime Interprime

Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap

First 100 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 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

List of prime numbers

This article is issued from Wikipedia - version of the Wednesday, March 02, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.