Cunningham-ketting

In de wiskunde is een Cunningham-ketting een 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 $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₁,...,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₁,...,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	p1 (laagste priemgetal)	Aantal cijfers	Jaar	Ontdekker
2	1st	48047305725×2172403 − 1	51910	2007	D. Underbakke
3	1st	164210699973×226326 − 1	7937	2006	M. Paridon
4	1st	119184698×5501# − 1	2354	2005	J. Sun
5	2nd	1719674368×1447# + 1	613	2004	D. Augustin
6	2nd	37783362904×1097# + 1	475	2006	D. Augustin
7	2nd	414792720846×557# + 1	237	2006	D. Augustin
8	1st	2×65728407627×431# − 1	186	2005	D. Augustin
9	1st	65728407627×431# − 1	185	2005	D. Augustin
10	2nd	145683282311×181# + 1	84	2005	D. Augustin
11	2nd	2×(8428860×127# + 212148902055091) − 1	56	2006	J. K. Andersen
12	2nd	8428860×127# + 212148902055091	56	2006	J. K. Andersen
13	1st	1753286498051×71# − 1	39	2005	D. Augustin
14	1st	9510321949318457733566099	25	2004	J. K. Andersen
15	1st	11993367147962683402919	23	2004	T. Alm, J. K. Andersen
16	1st	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 va 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.

Externe links

• 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 $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 $1\leq n\leq 15$

Bronnen, noten en/of referenties