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₁,...,p_n), zodat voor alle ${\displaystyle 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 ${\displaystyle p_{2}=2p_{1}+1}$, ${\displaystyle p_{3}=4p_{1}+3}$, ${\displaystyle p_{4}=8p_{1}+7}$, ..., ${\displaystyle 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₁,...,p_n) zodat voor alle ${\displaystyle 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₁,...,p_n) zodat voor alle ${\displaystyle 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.

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

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.^[1]

Laat het oneven priemgetal ${\displaystyle p_{1}}$ het eerste priemgetal van een Cunningham-ketting van de eerste soort zijn. Het eerste priemgetal is oneven, dus ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$. Omdat ieder volgende priemgetal in de ketting ${\displaystyle p_{i+1}=2p_{i}+1}$ is, volgt hieruit dat ${\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}}$. Dus, ${\displaystyle p_{2}\equiv 3{\pmod {4}}}$, ${\displaystyle 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 ${\displaystyle p_{i+1}=2p_{i}+1}$ in het tweetallig stelsel beschouwen, zien we dat, door ${\displaystyle p_{i}}$ met 2 te vermenigvuldigen, het minst significante cijfer van ${\displaystyle p_{i}}$ het op-een-na minst significante cijfer wordt van ${\displaystyle p_{i+1}}$. Omdat ${\displaystyle p_{i}}$ oneven is --en het minst significante cijfer dus 1 is binair-- weten we dat het op-een-na minst sigificante cijfer van ${\displaystyle 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:

Een soortgelijk resultaat is waar voor Cunningham-kettingen van de tweede soort. Uit de observatie dat ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$ en de relatie ${\displaystyle p_{i+1}=2p_{i}-1}$ volgt dat ${\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}}$. Binair eindigen alle priemgetallen in de ketting op "0...01", waarbij, voor iedere ${\displaystyle i}$, het aantal nullen in het patroon voor ${\displaystyle p_{i+1}}$ een meer is dan voor die in ${\displaystyle 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.

• The Prime Glossary: Cunningham chain
• PrimeLinks++: Cunningham chain
• Rij A005602 in OEIS: De eerste term van de laagste complete Cunningham-ketting van de eerste soort van lengte n, met ${\displaystyle 1\leq n\leq 14}$
• Rij A005603 in OEIS: De eerste term van de laagste complete Cunningham-ketting van de tweede soort van lengte n, met ${\displaystyle 1\leq n\leq 15}$