Cunningham-ketting

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 (p1,...,pn), zodat voor alle 1 <= i < n, pi+1 = 2 pi + 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 (p1,...,pn) zodat voor alle 1 <= i < n geldt: pi+1 = 2 pi - 1.

Cunningham-kettingen worden soms gegeneralizeerd naar rijen van priemgetallen (p1,...,pn) zodat voor alle 1 <= i < n, pi+1 = api + 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[bewerken]

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

Congruenties van Cunningham-kettingen[bewerken]

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 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} = 2 p_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[bewerken]

Bronnen, noten en/of referenties
  1. a b Dirk Augustin, Cunningham Chain records.