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 $1\le 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\le 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\le 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	1e	48047305725×2172403 − 1	51910	2007	D. Underbakke
3	1e	164210699973×226326 − 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(\mathrm{mod}2)$. Omdat ieder volgende priemgetal in de ketting $p_{i+1}=2p_i+1$ is, volgt hieruit dat $p_i\equiv 2^i-1(\mathrm{mod}{2}^i)$. Dus, $p_2\equiv 3(\mathrm{mod}4)$, $p_3\equiv 7(\mathrm{mod}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(\mathrm{mod}2)$ en de relatie $p_{i+1}=2p_i-1$ volgt dat $p_i\equiv 1(\mathrm{mod}{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\le n\le 14$
• Rij A005603 in OEIS: De eerste term van de laagste complete Cunningham-ketting van de tweede soort van lengte n, met $1\le n\le 15$