Temporal logic

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.

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{aligned}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{aligned}}$

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 or next term in the chain would not be a prime number anymore.

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

41, 83, 167 (The next number would be 335, 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, 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."

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.

Largest known Cunningham chain of length k (as of 14 December 2013)

k	Kind	p1 (starting prime)	Digits	Year	Discoverer
1		257885161 − 1	17425170	2013	Curtis Cooper, GIMPS
2	1st	18543637900515×2666667 − 1	200701	2012	Philipp Bliedung, PrimeGrid
	2nd	648309×2148310 + 1	44652	2010	Tom Wu
3	1st	914546877×234772 − 1	10477	2010	Tom Wu
	2nd	82659189×226997 + 1	8135	2010	Tom Wu
4	1st	1249097877×6599# − 1	2835	2011	Michael Angel
	2nd	630698711×4933# + 1	2105	2010	Michael Angel
5	1st	4250172704×2749# − 1	1183	2012	Dirk Augustin
	2nd	80670856865×2677# + 1	1140	2011	Michael Angel
6	1st	37488065464×1483# − 1	633	2010	Dirk Augustin
	2nd	37783362904×1097# + 1	475	2006	Dirk Augustin
7	1st	162597166369×827# − 1	356	2010	Dirk Augustin
	2nd	668302064×593# + 786153598231	251	2008	Thomas Wolter & Jens Kruse Andersen
8	1st	2×65728407627×431# − 1	186	2005	Dirk Augustin
	2nd	1148424905221×509# + 1	224	2010	Dirk Augustin
9	1st	65728407627×431# − 1	185	2005	Dirk Augustin
	2nd	182887101390961871050645934589918687746535370612015546956692154622371784133412186×223# + 1	167	2013	Primecoin (block 79349)
10	1st	44598464649019035883154084128331646888059795218766083584048621139159337786287845212160000×149# − 1	146	2013	Primecoin (block 182690)
	2nd	2361221366027763072635481564211745987513418780208430432809344944242307595601310582×139# + 1	137	2013	Primecoin (block 125775)
11	1st	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin (block 95569)
	2nd	8026337833619599372491948674562462668692014872229571339857384053514279156849912832×109# + 1	127	2014	Primecoin (block 365304)
12	1st	61592551716229060392971860549140211602858978086524024531871935735163762961673908480×71# − 1	110	2013	Primecoin (block 239833)
	2nd	160433998429454286861864982184342218645773889300991352796925862298096263175269000×73# + 1	109	2013	Primecoin (block 323183)
13	1st	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Primecoin (block 368051)
	2nd	457905006824220038355933583213167637693837605663532362031057034656375497233892960×37# + 1	94	2014	Primecoin (block 375981)
14	1st	9510321949318457733566099	25	2004	Jens Kruse Andersen
	2nd	335898524600734221050749906451371	33	2008	Jens Kruse Andersen
15	1st	662311489517467124375039	24	2008	Jaroslaw Wroblewski
	2nd	28320350134887132315879689643841	32	2008	Jaroslaw Wroblewski
16	1st	91304653283578934559359	23	2008	Jaroslaw Wroblewski
	2nd	2368823992523350998418445521	28	2008	Jaroslaw Wroblewski
17	1st	2759832934171386593519	22	2008	Jaroslaw Wroblewski
	2nd	1302312696655394336638441	25	2008	Jaroslaw Wroblewski

q# denotes the primorial 2×3×5×7×...×q.

Template:As of, the longest known Cunningham chain of either kind is of length 17. The first known was of the 1st kind starting at 2759832934171386593519, discovered by Jaroslaw Wroblewski in 2008 where he also found some of the 2nd kind.

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}=2p_{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.

See also

• Primecoin, which uses Cunningham chains as a proof-of-work system

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