backup del Post

Il problema 3n+1

Prendete il vostro linguaggio di programmazione favorito, o anche solo carta e penna, e iniziate a fare le seguenti operazioni (se siete tipi informatici, “implementate il seguente algoritmo”). Partite da un numero intero qualsiasi: se è dispari lo moltiplicate per 3 e poi aggiungete uno al risultato, ottenendo un numero pari; se è pari lo dimezzate, ottenendo… non si sa se un numero pari o dispari. Ripetete la cosa finché non ottenete un numero già visto (e quindi entrate in un ciclo infinito), oppure ottenete valori sempre più grandi, e quindi finite nello spazio numerico profondo. Cosa succederà?

Partendo da 1, otterremo 4, 2, 1; abbiamo trovato un ciclo di lunghezza 3. Con 2 ovviamente capita la stessa cosa; prendendo 3, avremo 10, 5, 16, 8, 4, 2, 1 e siamo di nuovo sul ciclo iniziale. Con 7, l’ottovolante dei numeri dà 22, 11, 34, 17, 52, 26, 13, 40, 20, 10… Toh, un numero già visto: anche stavolta insomma arriviamo al ciclo 1-2-4-1. Sarà sempre cosi? Non si sa. Il problema è noto come Congettura di Collatz, dal nome di chi propose nel 1937; ma è anche nota come “3n+1” (dall’operazione da fare quando si ha un numero dispari), o con tanti altri nomi diversi, il che mostra che ci hanno pensato su in tanti. D’altra parte, se Erdős affermò che “la matematica non è ancora pronta per problemi di questo tipo” e offrì ben 500$ a colei o colui che fosse riuscito a risolverlo vorrà ben dire qualcosa.

A dire il vero ci sono numeri di partenza che danno delle false speranze, mettendoci un bel po’ prima di stabizzarsi su quel ciclo; se volete divertirvi, provate a vedere cosa succede partendo da 27. Meglio usarla davvero, la calcolatrice: prima di arrivare a 1 ci sono 111 passi, e si arriva fino a 9232! Ma il destino sembra ineluttabile: come racconta Mathworld, la congettura è stata dimostrata per numeri fino a circa 5,48·10¹⁸ (no, non li hanno provati tutti, ci sono tecniche raffinate che permettono di saltare molti valori), e se c’è un ciclo diverso da quello banale esso deve contenere almeno 275000 valori; e a quanto ne so praticamente tutti i matematici, pur sapendo bene che l’evidenza numerica non serve a nulla, la ritengono vera.

Il bello è che basta cambiare di poco le condizioni iniziali per ottenere risultati diversi. Prendiamo ad esempio la non-congettura “3n-1”. Partendo da 1 otteniamo un ciclo 1-2, e partendo da 3 si passa da 8, 4, 2 prima di finire di nuovo nel ciclo; però se prendiamo come numero di partenza 5 il nostro viaggio passa per 14, 7, 20, 10, 5, e in questo caso abbiamo pertanto almeno due cicli possibili. Con la non-congettura “5n+1” la situazione è ancora peggiore; partendo da 7, infatti, il programmino che ho scritto in fretta e furia ha rapidamente superato il limite massimo dei numeri interi rappresentabili dal mio computer, e quindi immagino che i valori corrispondenti crescano senza limite. La cosa mi torna anche statisticamente; quando si arriva a un numero dispari il passo successivo ci porta a un numero pari dell’ordine di cinque volte quello iniziale; in metà dei casi il numero non è divisibile per 4 e quindi anche il secondo passo ci lascia un numero superiore a quello di partenza. Ammetto di non aver voglia di dimostrarlo formalmente, però…

Andando ancora più vicini a una soluzione, la non-congettura “3n+5” ha un ciclo che parte con 38, un numero non esattamente immaginabile a prima vista; e la stessa “3n+1”, se la estendiamo ai numeri negativi, ci dà tre ulteriori cicli che iniziano con -1, -5 e -17, oltre all’ovvio ciclo-pappagallo che ripete ad libitum “zero, zero, zero…”. Tutto questo può fare pensare che la mancanza di altri cicli sia proprio un caso, e probabilmente è proprio così: come molti problemi della teoria dei numeri, si pensi alla Congettura di Goldbach, non c’è una via maestra per risolverli proprio perché sono degli accidenti della storia dei numeri. Ciò non toglie che ci sia un’estesissima bibliografia al riguardo: se volete incominciare ad avere un’idea anche grafica di cosa si sa, date un’occhiata la pagina della successione delle lunghezze nell’On-Line Encyclopedia of Integer Sequences.