La congettura di Collatz; parte prima, la verifica software.**

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 2^{68}. 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.

Ho inserito questo codice di programmazione in questa pagina  web dinamica; potete divertirvi ad inserire dei numeri (non troppo grandi) per vedere la sequenza generata. Senza alcun  dubbio, alla fine della sequenza, otterrete sempre 1.
Un pò più complicato è il software che verifica la congettura per tutti i numeri interi da 1 a max, che non sarà di certo 2^{68}, nel nostro caso.  A parte la potenza del calcolatore, nella realtà verranno usate procedure ottimizzate, che permettono di capire in anticipo l’esito positivo della procedura. Comunque , usando il blocco illustrato nel diagramma di flusso, e aggiungendo una ripetizione di tale blocco con quello che si chiama in linguaggio tecnico “ciclo for”, è facile ottenere questo nuovo codice di programmazione:
 
Me.TextBox1.Text = “”
        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

 
 
sempre nella stessa pagina Web   potrete inserire il numero massimo di ripetizioni del blocco, che sarà anche il limite di validità della congettura. I risultati riportano anche il numero di ripetizioni fatte per arrivare a 1.  Chiaramente, avremo una conferma alla congettura solo se ogni procedura termina. Se il programma finisce in un ciclo da cui non può uscire, la congettura fallisce.
 
Bene, la seconda parte dell’articolo presenterà la forma più matematica della congettura, e un tentativo di soluzione, fatto da Terence Tao nel 2019, che userà dei ragionamenti riguardante la teoria dei grafi e il calcolo delle probabilità.
 

10 commenti su “La congettura di Collatz; parte prima, la verifica software.**”

  1. 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…

    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.

  2. 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…

    1. cos’ì com’ è no, non capisco. Dovresti commentare ed esplicitare , altrimenti resta solo un grafico, ma scommetto ci sia sotto qualcosa di interessante

  3. 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…

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

The maximum upload file size: 2 MB. You can upload: image, audio, video, document, spreadsheet, interactive, text, archive, code, other. Links to YouTube, Facebook, Twitter and other services inserted in the comment text will be automatically embedded.

 

Tag: