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.

Un pò più complicato è il software che verifica la congettura per tutti i numeri interi da 1 a max, che non sarà di certo , 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: