Giorni fa una mia cara amica e lettrice, mi ha reso edotto su una congettura riguardante la matematica elementare, tuttora irrisolto anche se verificato per grandi numeri al computer. Non mi vergogno nel dire che non lo conoscevo. Ho pensato di scrivere due articoli su questo problema; uno riguardante la verifica software, l’altro su una tentata dimostrazione di Terence Tao, abbastanza recente. Ma prima di tutto, vediamo cos’è la congettura di Collatz.
Collatz costruisce un facile algoritmo, che detto a parole risulta così:
Si prenda un numero (Intero positivo) , se è pari lo si divida per due, altrimenti lo si moltiplichi per tre e gli si aggiunga uno. Se il numero risultante da una delle due operazioni è maggiore di 1, si ripeta il procedimento. Qualsiasi sia il numero iniziale, alla fine delle iterazioni si ottiene sempre 1.
Per esempio, iniziando con n = 6, otteniamo la successione 6, 3, 10, 5, 16, 8, 4, 2, 1. La congettura di Collatz, dal punto di vista matematico, viene inquadrata nella teoria dei grafi. Ma la prima cosa che viene in mente di fare, è provare per grandi numeri queste iterazioni al computer. Non dimentichiamo che congetture ben più importanti, come quella di Thurston, furono provate prima al calcolatore, dando in questo caso esisto positivo. Poi arrivò Perelman a darne la dimostrazione matematica in seguito. Bene, anche la congettura di Collatz è stata provata al calcolatore, ed ha sempre generato esito positivo per numeri che che vanno da 2 a . Qui potete trovarne la storia dettagliata.
Ma noi ci occuperemo in questa prima parte della validità della frase “la congettura fu provata al calcolatore”. Cosa significa? E’ ora di sfatare il mito che il computer possa risolvere qualcosa che non può fare l’essere umano. Il sogno di Hilbert di affidare la matematica al calcolatore, fu distrutto da Godel, con i suoi teoremi di incompletezza.
I computer sono macchine stupide, se non fornite del software ideato dalla mente umana. Si tratta di tradurre l’algoritmo creato da Collatz, in procedure da far eseguire al computer. Ma andiamo per gradi. Costruiamo per primo un programmino che mi stampi la sequenza delle operazioni e controlli se il numero iniziale si trasformi nel numero 1. Per comprenderlo bene, usiamo quello che al tempo era molto in uso: un diagramma di flusso.
Se si dispone di un linguaggio di programmazione, è estremamente facile convertire tale algoritmo in un programma . Di seguito espongo anche il listato in codice VBnet di Visual studio:
Me.TextBox1.Text = “”
Dim n, r
n = Me.TextBox2.Text
If IsNumeric(n) Then
While n > 1
r = n Mod 2
If r = 0 Then
n = n / 2
Else
n = n * 3 + 1
End If
Me.TextBox1.Text = Me.TextBox1.Text & n & vbCrLf
End While
End If
in quasi tutti i linguaggi di programmazione esiste l’istruzione Mod, che dà semplicemente il resto della divisione di n per 2; se il resto è zero allora il numero è pari.
Dim n, r, i, max, j max = Me.TextBox3.Text If IsNumeric(max) Then
max = CInt(Me.TextBox3.Text)
For i = 1 To max
n = i
j = 0
While n > 1 r = n Mod 2
If r = 0 Then n = n / 2
Else
n = n * 3 + 1
End If j = j + 1 End While
Dim stringa
stringa = “n=” & i & “,” & ” Operazioni=” & j
Me.TextBox1.Text = Me.TextBox1.Text & stringa & vbCrLf
Next End If

Ho letto con piacere!! Aspetto la seconda parte 🙂
grazie! Ma sei tu l’artefice. Comunque sarà un pò dura la parte matematica.
Sarebbe bello sapere anche quanti numeri primi si incontrano nel percorso… oltre che visualizzare un grafico di numero operazioni…. (piccolo inciso… con 1… il numero operazioni==3)… una considerazione: qualsiasi numero dispari moltiplicato per 3 con la somma di 1 dovrebbe essere un numero pari…. mentre i numeri pari divisi per due sono alternativamente pari e dispari… di conseguenza mi sembra di intuire che vi saranno molte piu casualità di numeri pari presenti nella sequenza delle operazioni, quindi probabilmente si otterranno molte più divisioni che moltiplicazioni e quindi inevitabilmente, con una funzione regressiva si raggiungerà una gola massima che sarà sempre 2/2=1…
Posso verificarlo via software, provo a vedere. Poi aggiorno la pagina. Mi sembra cmq che non ci sia niente di sbagliato in ciò che dici intuitivamente . Proviamo a verificare.
ho aggiornato la pagina https://umbertocibien.org/math/collatz.aspx: effettivamente , mediamente i pari sono circa il doppio. Ma il tentativo di soluzione dato da Tao si appoggia su un suo articolo “Quasi tutte le orbite di Collatz raggiungono valori quasi limitati” . Se è così, intuitivamente poi possono convergere a 1.
Guarda un poco questo…. ti dice niente???
visto che ci sono… pubblico anche questo, che è una diretta conseguenza del precedente, con alpha = pari e beta = dispari…. devo dire che l’argomento intrippa molto… penso di continuare a trattarlo con qualche altro grafico… se ho tempo…
cos’ì com’ è no, non capisco. Dovresti commentare ed esplicitare , altrimenti resta solo un grafico, ma scommetto ci sia sotto qualcosa di interessante
Nel primo grafico ci sono in ascissa i primi 200 numeri ed in ordinata il numero dei cicli di risoluzione della funzione, mentre nel secondo grafico, sempre per i primi 200 numeri, in ordinata sono riportati in rosso i cicli di sequenza pari ed in verde i cicli di sequenze dispari per ogni numero la somma delle due sequenze equivale al numero dei cicli riportati sul primo grafico…. forse cercherò di fare anche un grafico con il trend di funzione per ogni numero… dove i picchi sono i numeri pari… dati dalla funzione di calcolo della base dispari…
ok, grazie. Ma a conclusioni dovremmo trarre?