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<sub>1</sub>, ..., p<sub>n</sub>) such that p<sub>i+1</sub>&nbsp;=&nbsp;2p<sub>i</sub>&nbsp;+&nbsp;1 for all 1&nbsp;≤&nbsp;i&nbsp;<&nbsp;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

: <math>

\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}

</math>

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

Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers (p<sub>1</sub>, ..., p<sub>n</sub>) such that p<sub>i+1</sub>&nbsp;=&nbsp;2p<sub>i</sub>&nbsp;−&nbsp;1 for all 1&nbsp;≤&nbsp;i&nbsp;<&nbsp;n.

It follows that the general term is

: <math>p_i = 2^{i-1}p_1 - (2^{i-1}-1).</math>

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

Cunningham chains are also sometimes generalized to sequences of prime numbers (p<sub>1</sub>, ..., p<sub>n</sub>) such that p<sub>i+1</sub> =&nbsp;ap<sub>i</sub>&nbsp;+&nbsp;b for all 1&nbsp;≤&nbsp;i&nbsp;≤&nbsp;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,&thinsp;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.)

: 89, 179, 359, 719, 1439, 2879 (The next number would be 5759, 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<sup>2</sup>, 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.

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.

{| class="wikitable sortable"

|+ Largest known Cunningham chain of length k (as of 18 February 2025)

|-

! k !! Kind !! p<sub>1</sub> (starting prime) !! Digits !! Year !! Discoverer

|-

| 1 || 1st / 2nd || 2<sup>136279841</sup> − 1 || align="right" | 41024320 || 2024 || Luke Durant, GIMPS

|-

| rowspan="2" | 2 || 1st || 2618163402417×2<sup>1290000</sup> − 1 || align="right" | 388342 || 2016 || PrimeGrid

|-

| 2nd || 213778324725×2<sup>561417</sup> + 1 || align="right" | 169015 || 2023 || Ryan Propper & Serge Batalov

|-

| rowspan="2" | 3 || 1st || 1128330746865×2<sup>66439</sup> − 1 || align="right" | 20013 || 2020 || Michael Paridon

|-

| 2nd || 214923707595×2<sup>49073</sup> + 1 || align="right" | 14784 || 2025 || Serge Batalov

|-

| rowspan="2" | 4 || 1st || 93003628384×10111# − 1 || align="right" | 4362 || 2025 || Serge Batalov

|-

| 2nd || 49325406476×9811# + 1 || align="right" | 4234|| 2019 || Oscar Östlin

|-

| rowspan="2" | 5 || 1st || 475676794046977267×4679# − 1 || align="right" | 2019 || 2024 || Andrey Balyakin

|-

| 2nd || 181439827616655015936×4673# + 1 || align="right" | 2018 || 2016 || Andrey Balyakin

|-

| rowspan="2" | 6 || 1st || 2799873605326×2371# − 1 || align="right" | 1016 || 2015 || Serge Batalov

|-

| 2nd || 37015322207094×2339# + 1 || align="right" | 1001 || 2025 || Serge Batalov

|-

| rowspan="2" | 7 || 1st || 82466536397303904×1171# − 1 || align="right" | 509 || 2016 || Andrey Balyakin

|-

| 2nd || 25802590081726373888×1033# + 1 || align="right" | 453 || 2015 || Andrey Balyakin

|-

| rowspan="2" | 8 || 1st || 89628063633698570895360×593# − 1 || align="right" | 265 || 2015 || Andrey Balyakin

|-

| 2nd || 2373007846680317952×761# + 1 || align="right" | 337 || 2016 || Andrey Balyakin

|-

| rowspan="2" | 9 || 1st || 553374939996823808×593# − 1 || align="right" | 260 || 2016 || Andrey Balyakin

|-

| 2nd || 173129832252242394185728×401# + 1 || align="right" | 187 || 2015 || Andrey Balyakin

|-

| rowspan="2" | 10 || 1st || 3696772637099483023015936×311# − 1 || align="right" | 150 || 2016 || Andrey Balyakin

|-

| 2nd || 2044300700000658875613184×311# + 1 || align="right" | 150 || 2016 || Andrey Balyakin

|-

| rowspan="2" | 11 || 1st || 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 || align="right" | 140 || 2013 || Primecoin (block 95569)

|-

| 2nd || 341841671431409652891648×311# + 1 || align="right" | 149 || 2016 || Andrey Balyakin

|-

| rowspan="2" | 12 || 1st || 288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1 || align="right" | 113 || 2014 || Primecoin (block 558800)

|-

| 2nd || 906644189971753846618980352×233# + 1 || align="right" | 121 || 2015 || Andrey Balyakin

|-

| rowspan="2" | 13 || 1st || 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 || align="right" | 107 || 2014 || Primecoin (block 368051)

|-

| 2nd || 38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1 || align="right" | 101 || 2014 || Primecoin (block 539977)

|-

| rowspan="2" | 14 || 1st || 4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1 || align="right" | 97 || 2018 || Primecoin (block 2659167)

|-

| 2nd || 5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1 || align="right" | 100 || 2014 || Primecoin (block 547276)

|-

| rowspan="2" | 15 || 1st || 14354792166345299956567113728×43# - 1 || align="right" | 45 || 2016 || Andrey Balyakin

|-

| 2nd || 67040002730422542592×53# + 1 || align="right" | 40 || 2016 || Andrey Balyakin

|-

| rowspan="2" | 16 || 1st || 91304653283578934559359 || align="right" | 23 || 2008 || Jaroslaw Wroblewski

|-

| 2nd || 2×1540797425367761006138858881 − 1 || align="right" | 28 || 2014 || Chermoni & Wroblewski

|-

| rowspan="2" | 17 || 1st || 2759832934171386593519 || align="right" | 22 || 2008 || Jaroslaw Wroblewski

|-

| 2nd || 1540797425367761006138858881 || align="right" | 28 || 2014 || Chermoni & Wroblewski

|-

| 18 || 2nd || 658189097608811942204322721 || align="right" | 27 || 2014 || Chermoni & Wroblewski

|-

| 19 || 2nd || 79910197721667870187016101 || align="right" | 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.

See also

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

References