Network Bar

martedì 23 febbraio 2016

La grandinata di numeri

Praticamente tutti, tra matematici professionisti e amatoriali, hanno prima o poi messo le mani sulla famosa congettura di Collatz. Enunciarla, come ha anche scritto Michele nel post dedicato alla congettura inversa, è abbastanza semplice:
Scelgliete un qualunque intero positivo $n$. Se il numero è dispari, moltiplicatelo per tre e aggiungete 1, $3n+1$, altrimenti se è pari dividetelo per 2, $n/2$. Continuate la procedura con il nuovo numero così ottenuto.
Dopo un po' di tentativi ci si accorge abbastanza presto che esiste una sequenza dentro la quale, una volta caduti, non si esce più, un vero e proprio loop numerico, ovvero 4, 2, 1. In pratica la congettura di Collatz afferma che qualunque sia il numero $n$ di partenza, la sequenza si concluderà invariabilmente con il loop 4, 2, 1.
Il nome della congettura viene dal matematico tedesco Lothar Collatz, il primo a proporla nel 1937, ma non fu il solo a scoprirla. L'elenco comprende personalità come il fisico Stanislaw Ulam o il matematico Shizuo Kakutani o ancora il matematico Bryan Thwaites, mentre fu il collega di Collatz Helmut Hasse che introdusse la congettura presso l'università di Syracuse, da cui problema di Syracuse. La sequenza è invece chiamata sequenza dei chicchi di grandine (hailstone sequence), a causa delle soventi discese e risalite, come si può apprezzare nella sequenza generata dal 27:
Questo andamento apparentemente casuale è una delle difficoltà nella ricerca di una dimostrazione rigorosa, ma non l'unica.
Altro ostacolo è l'assenza di una regolarità nelle sequenze stesse: la loro lunghezza, intesa come numero di passi necessari per raggiungere 1, è variabile, mentre lo stesso numero massimo raggiunto da ciascuna sequenza è differente e non regolare. Ad esempio uno dei massimi più presenti è il 9232 (generato, tra gli altri, dalla sequenza del 27 di cui sopra), mentre la sequenza generata dal 26623 ha come massimo 106358020 (lo stesso massimo della sequenza del 52527) e quella generata dal 34239 ha come massimo "solo" 18976192. Quindi, come potete comprendere, questi "alti e bassi" che si osservano in ogni singola sequenza, sono presenti anche quando si cercano di comprendere le proprietà della procedura di Collatz.
In un certo senso, però, la procedura di Collatz sembra mostrare una sorta di invarianza di scala. Non uso a caso questo concetto, perché se la si applica ai numeri complessi (coinvolgendo le funzioni trigonometriche) si genera il frattale di Collatz:
Un altro paio di interessanti osservazioni fornite da Jeffrey Lagaris sono legate ai tassi di crescita e di decrescita delle sequenze: il valore, infatti, sembra crescere di un fattore 3/2 per iterazione, e diminuire di un fattore 3/4 ad ogni iterazione. Queste sono osservazioni di tipo euristico, che però sono state successivamente confermate dalle osservazioni sperimentali, che nel caso della matematica dei numeri vogliono dire realizzate attraverso l'ausilio di calcolatori. Grazie ai linguaggi di programmazione che il loro uso ha diffuso sempre più anche nei dipartimenti di matematica, è possibile scrivere un piccolo programma in grado di calcolare e visualizzare una sequenza a partire da un dato numero iniziale. Cuore del programma è, evidentemente, la riga di codice che descrive la procedura di Collatz. Ad esempio Brian Hayes propone la sequente riga in BASIC
IF N MOD 2 = 0 THEN N = N/2 ELSE N = 3 * N +1
Ovviamente, a parte l'impossibilità di ottenere una dimostrazione conclusiva, ci sono due importanti difficoltà nell'aproccio informatico alla procedura di Collatz, una abbastanza semplice da gestire, ovvero il loop, e l'altra un po' meno semplice legata alla potenza di calcolo. Data, infatti, la semplicità della congettura, non è possibile semplificare la procedura in modo da ridurre il tempo di elaborazione grazie al software, e quindi bisogna in qualche modo pazientare o avere un hardware sufficientemente potente.
Esistono, però, dei programmini che permettono con numeri relativamente bassi di ottenere rapidamente le sequenze di Collatz relative, come ad esempio quella del 95 ottenuta con l'hailstone evaluator del plus magazine:
95, 286, 143, 430, 215, 646, 323, 970, 485, 1456, 728, 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, 4, 2, 1,...

Brian Hayes (1983). Computer Recreations Scientific American, 249 (4), 22-36 DOI: 10.1038/scientificamerican1083-22

Nessun commento:

Posta un commento