Don't take life too seriously: it's just a temporary situation

Catene di Cunningham di prima specie

Teoria dei numeri 

Un primo di Sophie Germain è un primo p tale che 2p + 1 sia primo; se continuando a raddoppiare e sommare 1 per alcune volte si ottengono numeri primi, la sequenza risultante si dice “catena di Cunningham di prima specie” o semplicemente “catena di Cunningham”, in onore di Allan Cunningham. Per esempio, 2, 5, 11, 23 e 47 formano una catena di Cunningham di prima specie.

Cunningham trovò nel 1907 le catene di lunghezza 6 che iniziano con 89, 63419 e 127139; ci volle oltre mezzo secolo per superare tale record: nel 1965 D.H. Lehmer trovò le prime catene di lunghezza 7.

 

Tutti i primi di una catena di Cunningham di prima specie tranne l’ultimo sono primi di Sophie Germain.

 

Non possono esistere catene di Cunningham di prima specie di lunghezza infinita, ma dalla congettura di Dickson segue che ne esistono infinite di qualsiasi lunghezza; la più lunga nota, trovata da Jaroslaw Wroblewski nel 2008, comprende 17 primi e inizia con 2759832934171386593519.

 

In base 2 i primi che compongono una catena di Cunningham di prima specie si rappresentano aggiungendo ogni volta un 1 a destra del precedente. Per esempio, i primi che compongono la catena che inizia con 509 si rappresentano così: 1111111012 = 509, 11111110112 = 1019, 1111111011112 = 2039, 11111110111112 = 4079.

 

Tranne 2 e 3 nessun primo può far parte sia di una catena di Cunningham di prima specie, sia di una catena di Cunningham di seconda specie.

 

Si conoscono catene di 3 primi tutti palindromi; il minimo valore iniziale possibile è 19091918181818181919091 (Dubner, 1994); il massimo noto è 1818181808080818080808180818081818081808181818081808080818180808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080818180808081808181818081808181808180818080808180808081818181 (Dubner 1999); da notare che il numero di cifre, 727, è pure palindromo.

Non possono esistere catene di palindromi di 4 o più primi, perché almeno un numero finirebbe con la cifra 5 e non sarebbe primo.

 

La tabella seguente riporta i primi iniziali delle catene di Cunningham di prima specie di lunghezza almeno 3 minori di 10000.

Primo iniziale

Lunghezza della catena

2

5

5

4

11

3

41

3

89

6

179

5

359

4

509

4

719

3

1019

3

1031

3

1229

4

1409

4

1451

3

1481

3

1511

3

1811

3

1889

3

1901

3

1931

3

2459

3

2699

4

2819

3

3449

3

3491

3

3539

4

3821

3

3911

3

5081

3

5399

3

5441

3

5849

3

6101

3

6131

3

6449

4

7079

3

7151

3

7349

3

7901

3

8969

3

9221

3

 

La tabella mostra il minimo primo in una catena di esattamente n termini (Jack Brennen, Paul Jobling e N.J.A. Sloane, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Minimo primo

1

13

2

3

3

41

4

509

5

2

6

89

7

1122659

8

19099919

9

85864769

10

26089808579

11

665043081119

12

554688278429

13

4090932431513069

14

95405042230542329

15

113220800675069784839

16

810433818265726529159

 

La tabella seguente riporta le massime catene note.

Primo iniziale

Cifre

Scopritori e anno

Lunghezza della catena

2618163402417 • 21290000 − 1

388342

Brown (PrimeGrid), 2016

2

18543637900515 • 2666667 – 1

200701

Bliedung (PrimeGrid), 2012

2

183027 • 2265440 − 1

79911

Tom Wu, 2010

2

778965587811 • 236625 – 1

11038

Angel, D. Augustin, 2016

3

272879344275 • 236620 – 1

11036

Angel, D. Augustin, 2016

3

333645655005 • 235547 – 1

10713

Batalov, 2015

3

5110664609396115 • 234944 – 1

10536

Gábor Farkas, Gábor E. Gévay, Antal Járai e Emil Vatai, 2014

3

914546877 • 234772 – 1

10477

Tom Wu, 2010

3

28961560189 • 7517# – 1

3218

Angel, D. Augustin, 2016

4

28904981097 • 6703# – 1

2882

Batalov , 2015

4

1249097877 • 6599# – 1

2835

Angel, 2011

4

119184698 • 5501# – 1

2354

J. Sun, 2005

4

2554760770 • 3733# – 1

1605

Angel, 2010

4

199949435137 • 3499# – 1

1493

Östlin, 2016

5

361296035282 • 3023# – 1

1299

Batalov , 2015

5

4250172704 • 2749# – 1

1183

D. Augustin, 2012

5

587027392600 • 2477# – 1

1070

Östlin, 2016

5

533799816556 • 2477# – 1

1070

Östlin, 2016

5

2799873605326 • 2371# – 1

1016

Batalov , 2015

6

37488065464 • 1483# − 1

633

D. Augustin, 2010

6

1882807711450 • 1327# – 1

578

Batalov , 2014

6

82466536397303904 • 1171# – 1

509

Balyakin, 2016

7

3931472185692005387730944 • 857# – 1

381

Balyakin, 2015

7

14317181455772 • 853# – 1

367

Batalov , 2014

7

162597166369 • 827# − 1

356

D. Augustin, 2010

7

89628063633698570895360 • 593# – 1

265

Balyakin, 2015

8

2 • 553374939996823808 • 593# – 1

260

Balyakin, 2016

8

5175268103676 • 557# – 1

238

Östlin, 2015

8

553374939996823808 • 593#-1

260

Balyakin, 2016

9

40912747216912409971130368 • 401# – 1

190

Balyakin, 2015

9

2630705556345975695872 • 401# – 1

186

Balyakin, 2015

9

65728407627 • 431# − 1

185

D. Augustin, 2005

9

3696772637099483023015936 • 311# − 1

150

Balyakin, 2016

10

380036435653000196587520 • 311# − 1

149

Balyakin, 2016

10

1814165079257305081195008 • 307# − 1

148

Balyakin, 2015

10

73853903764168979088206401473739410396455001112581722569026969860983656346568919 • 151# − 1

140

Primecoin, 2013

11

397146194319432735351828361368498572415833839171716172868658515395849798889548375 • 107# − 1

124

Primecoin, 2013

11

239744775802122662005054501673219419476327706093461245474933836166272232010143904 • 107# − 1

123

Primecoin, 2015

11

288320466650346626888267818984974462085357412586437032687304004479168536445314040 • 83# − 1

113

Primecoin, 2014

12

61592551716229060392971860549140211602858978086524024531871935735163762961673908480 • 71# − 1

110

Primecoin, 2013

12

178811043947926524937518051044987491022433869417704220317907704222148116972528580 • 71# − 1

107

Primecoin, 2014

12

106680560818292299253267832484567360951928953599522278361651385665522443588804123392 • 61# − 1

107

Primecoin, 2014

13

130083778959343562529131897703476422909096253953040587242097712006102296570026924 • 59# − 1

102

Primecoin, 2014

13

19313073314471398368420651854042490322517950973521740350204774005412663648863502336 • 47# − 1

101

Primecoin, 2014

13

1753286498051 • 71# − 1

39

D. Augustin, 2005

13

55542261524672286885696 • 73# − 1

52

Balyakin, 2016

14

2 •14354792166345299956567113728 • 43# − 1

45

Balyakin, 2016

14

114575411943216666676166656 • 47# − 1

44

Balyakin, 2016

14

14354792166345299956567113728 • 43# − 1

45

Balyakin, 2016

15

14366587870229772953764096 • 43# − 1

42

Balyakin, 2015

15

27353790674175627273118204975428644651729

41

Jaroslaw Wroblewski, 2014

15

91304653283578934559359

23

Jaroslaw Wroblewski, 2008

16

2 • 2759832934171386593519 + 1

22

Jaroslaw Wroblewski, 2008

16

892390227741617675069

21

Carmody e Jobling, 2002

16

2759832934171386593519

22

Jaroslaw Wroblewski, 2008

17

 

Alcuni metodi per dimostrare che un intero p è primo richiedono la scomposizione di p + 1 o p – 1; se tale numero contiene a sua volta un primo molto grande, la dimostrazione si complica, perché bisogna ripetere il procedimento con un numero di poco più piccolo di quello iniziale. I massimi numeri di una catena di Cunningham di prima o seconda specie rappresentano quindi i casi peggiori per tali metodi.

 

Sono state cercate anche catene di forma leggermente diversa; se da p si passa a 2p2 + 1, il numero risultante è sempre multiplo di 3.

Se invece da p si passa a 4p2 + 1:

  • la minima catena di lunghezza esattamente 2 inizia con 2, la minima che inizi da un primo dispari inizia con 5;

  • la minima catena di lunghezza esattamente 3 inizia con 3;

  • la minima catena di lunghezza 4 inizia con 13;

  • la minima catena di lunghezza 5 inizia con 9220303.

 

Lenny Jones dimostrò nel 2011 che esiste l’equivalente delle catene di Cunningham di prima specie tra i polinomi, ossia esistono sequenze di polinomi pn(x), tali che pn + 1(x) = xpn(x) + 1, nei quali i primi k termini sono irriducibili, mentre il termine successivo è riducibile.

In particolare per m > 1 i primi k termini della sequenza di polinomi che inizia con Primo termine della sequenza di polinomi sono irriducibili, il successivo è riducibile, quindi questi polinomi formano una catena di lunghezza k. Se p è primo, la sequenza di polinomi che inizia con p1(x) = px + 1 costituisce una catena di lunghezza infinita.

Esistono quindi infinite catene di polinomi di qualsiasi lunghezza e infinite catene di lunghezza infinita.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.