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

Collatz (congettura di)

Congetture  Vari 

Il matematico tedesco Lothar Collatz (Arnsberg, Germania, 6/7/1910 – Varna, Bulgaria, 26/9/1990) inventò un procedimento all’apparenza banale, dal quale nacque uno dei più difficili problemi dell’aritmetica elementare.

Il procedimento consiste nel prendere un intero positivo, dividerlo per 2 se è pari, triplicarlo e sommare 1 se è dispari, ripetendo il tutto con il numero ottenuto.

Per esempio, iniziando con 22 si ottiene la sequenza 22, 11, 34, 17, 52, 26, 13, 40, 20, 20, 5, 16, 8, 4, 2, 1.

 

La congettura di Collatz è che partendo da un qualsiasi intero positivo si arrivi sempre a 1, dopodichè si resta intrappolato nel ciclo 1, 4, 2.

La congettura è anche nota come “congettura di Ulam”, “problema di Kakutani”, “congettura di Thwaites”, “algoritmo di Hasse”, dal nome di esperti che la trattarono, ma anche come “problema di Siracusa” o “congettura del chicco di grandine”, perché in generale i numeri ottenuti salgono e scendono, come chicchi di grandine in un temporale, prima di cadere al suolo (ossia a 1).

 

Data la semplicità della procedura, la congettura ha attirato molta attenzione da parte di appassionati e matematici esperti; nel 1999 si è svolta la prima conferenza internazionale dedicata al problema.

Finora vi sono stati piccoli progressi e qualche tentativo di dimostrazione, rivelatosi errato.

 

Partendo da interi differenti si ottengono sequenze irregolari e molto diverse tra loro; per esempio, iniziando con 27 si arriva a 1 in 111 passi, toccando un massimo uguale a 9232: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

 

La congettura è stata verificata fino a 5 • 260 = 5764607523034234880 da Tomás Oliveira e Silva nel 2009 e sussistono pochi dubbi che sia vera, tuttavia numerosi esperti hanno espresso il parere che la sua dimostrazione sia completamente al di fuori della portata delle tecniche note.

 

La tabella seguente riporta il numero di passi per arrivare a 1 e il massimo raggiunto partendo dagli interi fino a 20.

Numero iniziale

Numero di passi

Massimo raggiunto

1

0

1

2

1

2

3

7

16

4

2

4

5

5

16

6

8

16

7

16

52

8

3

8

9

19

52

10

6

16

11

14

52

12

9

16

13

9

40

14

17

52

15

17

160

16

4

16

17

12

52

18

20

52

19

20

88

20

7

20

 

La tabella seguente riporta i minimi numeri che richiedono n passi per arrivare a 1, per n fino a 20.

n

Numero

0

1

1

2

2

4

3

8

4

16

5

5

6

10

7

3

8

6

9

12

10

24

11

48

12

17

13

34

14

11

15

22

16

7

17

14

18

28

19

9

20

18

 

La tabella seguente mostra gli interi che richiedono più passi di tutti i precedenti per arrivare a 1 (Eric Roosendaal, http://www.ericr.nl/wondrous/index.html).

Numero

Passi

2

1

3

7

6

8

7

16

9

19

18

20

25

23

27

111

54

112

73

115

97

118

129

121

171

124

231

127

313

130

327

143

649

144

703

170

871

178

1161

181

2223

182

2463

208

2919

216

3711

237

6171

261

10971

267

13255

275

17647

278

23529

281

26623

307

34239

310

35655

323

52527

339

77031

350

106239

353

142587

374

156159

382

216367

385

230631

442

410011

448

511935

469

626331

508

837799

524

1117065

527

1501353

530

1723519

556

2298025

559

3064033

562

3542887

583

3732423

596

5649499

612

6649279

664

8400511

685

11200681

688

14934241

691

15733191

704

31466382

705

36791535

744

63728127

949

127456254

950

169941673

953

226588897

956

268549803

964

537099606

965

670617279

986

1341234558

987

1412987847

1000

1674652263

1008

2610744987

1050

4578853915

1087

4890328815

1131

9780657630

1132

12212032815

1153

12235060455

1184

13371194527

1210

17828259369

1213

31694683323

1219

63389366646

1220

75128138247

1228

133561134663

1234

158294678119

1242

166763117679

1255

202485402111

1307

404970804222

1308

426635908975

1321

568847878633

1324

674190078379

1332

881715740415

1335

989345275647

1348

1122382791663

1356

1444338092271

1408

1899148184679

1411

2081751768559

1437

2775669024745

1440

3700892032993

1443

3743559068799

1549

7487118137598

1550

7887663552367

1563

10516884736489

1566

14022512981985

1569

19536224150271

1585

26262557464201

1588

27667550250351

1601

38903934249727

1617

48575069253735

1638

51173735510107

1651

60650353197163

1659

80867137596217

1662

100759293214567

1820

134345724286089

1823

223656998090055

1847

397612441048987

1853

530149921398649

1856

706866561864865

1859

942488749153153

1862

1256651665537537

1865

1675535554050049

1868

2234047405400065

1871

2978729873866753

1874

3586720916237671

1895

4320515538764287

1903

4861718551722727

1916

6482291402296969

1919

7579309213675935

1958

12769884180266527

2039

17026512240355369

2042

22702016320473825

2045

45404032640947650

2046

46785696846401151

2090

93571393692802302

2091

104899295810901231

2254

209798591621802462

2255

279731455495736617

2258

 

Nonostante il numero di passi vari in maniera irregolare, vi sono sequenze di numeri consecutivi che richiedono lo stesso numero di passi per arrivare a 1.

La tabella seguente riporta la minima sequenza di esattamente n interi consecutivi che richiedano lo stesso numero di passi, per n fino a 20.

n

Minimo intero

Numero di passi

1

1

0

2

12

9

3

28

18

4

314

37

5

98

25

6

386

120

7

943

36

8

1494

47

9

1680

42

10

4722

59

11

6576

137

12

11696

143

13

3982

51

14

2987

48

15

17548

141

16

36208

41

17

7083

57

18

59692

73

19

159116

77

20

79592

76

 

Se il massimo raggiunto iniziando da n è maggiore di 3n + 1, è della forma 36k + 16.

 

E’ stato dimostrato che se esistono interi partendo dai quali la procedura non si arresta, il numero di quelli minori di n è al massimo cn1 – 0.05004, per una costante c (Riho Terras, 1976).

 

La congettura ha due forme: quella debole afferma che iniziando da qualsiasi intero positivo si finisce in un ciclo in un numero finito di passi, quella forte che l’unico ciclo è costituito da 1, 4, 2.

 

C. Böhm e G. Sontacchi considerarono nel 1978 la possibilità di iniziare da interi negativi, dimostrarono che il numero di cicli di lunghezza n è al massimo 2n e avanzarono la congettura che gli unici cicli siano:

  • –17, –50, –25, –74, –37, –110, –55, –164, –82, –41, –122, –61, –182, –91, –272, –136, –68, –34;

  • –5, –14, –7, –20, –10;

  • 0;

  • 1, 4, 2.

I due matematici dimostrarono che il fatto che questo ciclo sia l’unico con interi maggiori di zero è equivalente all’affermazione che non esiste una sequenza finita di interi crescenti a1 = 0, a2, a3, … ak + 1 tale che per un intero n maggiore di 1 valga Equazione che non ha soluzioni intere se il ciclo 1, 4, 2 è l'unico con interi positivi.

 

Nel 1978 R.P. Steiner dimostrò che il ciclo 1, 4, 2 ciclo è l’unico nel quale vi sia un solo intero maggiore del precedente, quindi con una sola sottosequenza ascendente e una discendente.

John L. Simons e B. de Weger dimostrarono nel 2003 che non esistono cicli con al massimo 68 sottosequenze ascendenti e altrettante discendenti.

E’ stato dimostrato che se esistono altri cicli, contengono più di 275000 numeri.

 

Indicando con p(n) il numero di termini pari nella sequenza che inizia con n e con d(n) il numero di quelli dispari (escludendo l’uno finale), vale d(n) / p(n) < log(2) / log(3).

 

Il residuo r(n) di n è definito come Formula per la definizione di r(n). Il residuo è quasi sempre un numero compreso tra 1.1 e 1.25 e questo ha spinto gli esperti a proporre la congettura che esistano interi tali che il loro residuo sia maggiore di quello di tutti gli altri interi; se fosse vero sarebbero infiniti, perché per ogni valore di k r(2kn) = r(n). La forma forte di questa congettura è che il massimo residuo si raggiunga per n = 993: r(993) = 2^61 / (3^32 * 993); se esiste un intero con un residuo maggiore, è maggiore di 1017.

 

La speranza di arrivare a una soluzione tramite una qualche forma di ricerca con l’aiuto di calcolatori elettronici è stata molto indebolita da John Horton Conway. Il matematico considerò semplici generalizzazioni del procedimento di Collatz, nelle quali a ogni passo si sostituisce n con f(n) = akn + bk, dove k = n mod p e i vari ak e bk sono numeri razionali, scelti in modo tale che f(n) sia sempre un intero (la procedura originale di Collatz corrisponde al caso p = 2, a(0) = 1 / 2, b0 = 0, a1 = 3, b1 = 1). Conway dimostrò nel 1972 che per alcune scelte di p e dei vari ak e bk il problema di stabilire se partendo da un intero n si raggiunga 1 è indecidibile, ossia non esiste una macchina di Turing capace di deciderlo in un numero finito di passi.

 

Nel 2007 Eero Lehtonen studiò una semplice variante della procedura di Collatz, nella quale se il numero è dispari lo si triplica e si somma un intero tra –9 e 9, a seconda di quale tra 19 insiemi infiniti contenga n; Lehtonen dimostrò che il problema di stabilire se si arrivi a 1 partendo da un intero n è indecidibile.

 

Stuart A. Kurtz e Janos Simon dimostrarono nel 2007 che il problema è indecidibile in un senso anche più forte e resta tale se si fissa p = 6480.

 

La procedura di Collatz può essere vista come l’iterazione della funzione f(z) = (7 * z + 2 – (5 * z + 2) * cos(π * z)) / 4, limitata ad argomenti interi. Iterando la funzione, si trova che diverge per alcuni valori iniziali di z e converge per altri; colorando i punti del piano complesso in nero, se l’iterazione diverge utilizzando quel punto come valore iniziale e con colori differenti se converge, si ottiene un disegno, riportato nella figura seguente (Pokipsy76 – English wikipedia, Public Domain, https://commons.wikimedia.org/w/index.php?curid=7188269), che ricorda in vari particolari quello dell’insieme di Mandelbrot (v. costante di Mandelbrot).

 

Raffigurazione dell'insieme ottenuto dalla procedura di Collatz

Contattami

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