# Cunningham-ketting

In de wiskunde is een Cunningham-ketting een bepaald type deelrij van de priemgetallen. Cunningham-kettingen zijn genoemd naar de wiskundige A. J. C. Cunningham Ze worden ook wel kettingen van bijna dubbele priemgetallen genoemd.
Een Cunningham-ketting van de eerste soort van lengte n is een rij van priemgetallen (p$_1$,...,p$_n$), zodat voor alle $1\leq i<n$, p$_{i+1}$ = 2 p$_i$ + 1. Hieruit volgt dat alle elementen in de rij Sophie-Germain priemgetallen zijn, op het laatste na, en alle priemgetallen op het eerste na zijn veilige priemgetallen.
Het is duidelijk dat $p_{2}=2p_{1}+1$, $p_{3}=4p_{1}+3$, $p_{4}=8p_{1}+7$, ..., $p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)$.
Op dezelfde manier is een Cunningham-ketting van de tweede soort van lengte n een rij van priemgetallen (p$_1$,...,p$_n$) zodat voor alle $1\leq i<n$ geldt: p$_{i+1}$ = 2 p$_i$ - 1.
Cunningham-kettingen van de eerste en tweede soort kunnen worden gegeneraliseerd naar rijen van priemgetallen (p$_1$,...,p$_n$) zodat voor alle $1\leq i<n$, p$_{i+1}$ = ap$_i$ + b voor vaste onderling ondeelbare getallen a, b; het resultaat noemen we een gegeneraliseerde Cunningham-ketting.
Een Cunningham-ketting is compleet als hij niet verder uitgebreid kan worden, dat wil zeggen als de vorige en de volgende getallen in de ketting niet meer priem zouden zijn.

## Grootste bekende Cunningham-kettingen

Volgens het vermoeden van Dickson en de bredere Schinzel's Hypothese H, zijn er voor iedere k oneindig veel Cunninghamkettingen van lengte k. Er zijn echter geen methoden bekend om deze kettingen te genereren
Grootste bekende Cunningham-ketting van lengte k (Juni 2007) :
| k | Soort | p$_1$ (laagste priemgetal) | Aantal cijfers | Jaar | Ontdekker |
| 2 | 1e | 48047305725×2$^{172403}$ − 1 | 51910 | 2007 | D. Underbakke |
| 3 | 1e | 164210699973×2$^{26326}$ − 1 | 7937 | 2006 | M. Paridon |
| 4 | 1e | 119184698×5501# − 1 | 2354 | 2005 | J. Sun |
| 5 | 2e | 1719674368×1447# + 1 | 613 | 2004 | D. Augustin |
| 6 | 2e | 37783362904×1097# + 1 | 475 | 2006 | D. Augustin |
| 7 | 2e | 414792720846×557# + 1 | 237 | 2006 | D. Augustin |
| 8 | 1e | 2×65728407627×431# − 1 | 186 | 2005 | D. Augustin |
| 9 | 1e | 65728407627×431# − 1 | 185 | 2005 | D. Augustin |
| 10 | 2e | 145683282311×181# + 1 | 84 | 2005 | D. Augustin |
| 11 | 2e | 2×(8428860×127# + 212148902055091) − 1 | 56 | 2006 | J. K. Andersen |
| 12 | 2e | 8428860×127# + 212148902055091 | 56 | 2006 | J. K. Andersen |
| 13 | 1e | 1753286498051×71# − 1 | 39 | 2005 | D. Augustin |
| 14 | 1e | 9510321949318457733566099 | 25 | 2004 | J. K. Andersen |
| 15 | 1e | 11993367147962683402919 | 23 | 2004 | T. Alm, J. K. Andersen |
| 16 | 1e | 892390227741617675069 | 21 | 2002 | P. Carmody, P. Jobling |
q# betekent de primoriaal 2×3×5×7×...×q.
In Juni 2007, de langste bekende Cunningham-ketting van beide soorten is van lengte 16. Zo'n ketting van de tweede soort was ontdekt door Tony Forbes in 1997, beginnend met 3203000719597029781. Een ketting van de eerste soort was ontdekt door Phil Carmody en Paul Jobling in 2002, beginnend met 810433818265726529159.

## Congruenties van Cunningham-kettingen

Laat het oneven priemgetal $p_{1}$ het eerste priemgetal van een Cunningham-ketting van de eerste soort zijn. Het eerste priemgetal is oneven, dus $p_{1}\equiv 1{\pmod {2}}$. Omdat ieder volgende priemgetal in de ketting $p_{i+1}=2p_{i}+1$ is, volgt hieruit dat $p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}$. Dus, $p_{2}\equiv 3{\pmod {4}}$, $p_{3}\equiv 7{\pmod {8}}$, enzovoort...
De hierboven genoemde eigenschap kan informeel worden waargenomen door de priemgetallen in een ketting in het binair talstelsel te observeren. (Merk op dat, zoals in ieder talstelsel, een vermenigvuldiging met de basis de cijfers in het getal naar links "schuift".) Wanneer we $p_{i+1}=2p_{i}+1$ in het tweetallig stelsel beschouwen, zien we dat, door $p_{i}$ met 2 te vermenigvuldigen, het minst significante cijfer van $p_{i}$ het op-een-na minst significante cijfer wordt van $p_{i+1}$. Omdat $p_{i}$ oneven is --en het minst significante cijfer dus 1 is binair-- weten we dat het op-een-na minst sigificante cijfer van $p_{i+1}$ ook 1 is. Zo kunnen we zien dat het getal steeds naar links wordt verschoven en er een achter wordt gezet. Hier is bijvoorbeeld de complete ketting met lengte 6 die begint met 141361469:
| Binair | Decimaal |
| 1000011011010000000100111101 | 141361469 |
| 10000110110100000001001111011 | 282722939 |
| 100001101101000000010011110111 | 565445879 |
| 1000011011010000000100111101111 | 1130891759 |
| 10000110110100000001001111011111 | 2261783519 |
| 100001101101000000010011110111111 | 4523567039 |
Een soortgelijk resultaat is waar voor Cunningham-kettingen van de tweede soort. Uit de observatie dat $p_{1}\equiv 1{\pmod {2}}$ en de relatie $p_{i+1}=2p_{i}-1$ volgt dat $p_{i}\equiv 1{\pmod {2^{i}}}$. Binair eindigen alle priemgetallen in de ketting op "0...01", waarbij, voor iedere $i$, het aantal nullen in het patroon voor $p_{i+1}$ een meer is dan voor die in $p_{i}$. Net zoals bij de Cunningham-kettingen van de eerste soort, schijven de bits links van het patroon een positie naar links met ieder volgende priemgetal.