[HOME - BASE Cinque - Appunti di Matematica ricreativa]

L'algoritmo di Collatz

Una sequenza scoperta da Lothar Collatz
e diffusa da Helmut Hasse, Stanislaw Ulam, S. Kakutani

questa pagina contiene codice javascript
può essere scaricata ed eseguita senza essere collegati ad internet

Grazie a Peppe per averci ricordato questo problema.
Il problema era già stato proposto da Gianvittorio Righi nelle Ricreazioni ricevute di Marzo 2001 (41. Ma perché sempre 1?)

L'algoritmo di Collatz

Che succede?

Ad esempio: partiamo da 7.
E' dispari, quindi faccio 3x7+1=22.
Pari, 22:2=11.
Dispari, 11x3+1=34.
Pari, 34:2=17.
Dispari, 17x3+1=52.
Pari, 26.
Pari, 13.
Dispari, 40.
Pari, 20.
Pari, 10.
Pari, 5.
Dispari, 16.
Pari, 8.
Pari, 4.
Pari, 2.
Pari, 1.
Da questo punto in poi non succede più nulla perché viene fuori sempre 4,2,1,4,2,1,4,2,1.....

L'algoritmo di Collatz in javascript

Numero di partenza

 digita il numero e clicca sul pulsante Calcola!

Valore massimo

Numeri pari

Numero di cicli

Numeri dispari
   

Rapporto p/d

Sequenza risultato

Codice javascript di Gianfranco Bo

La congettura di Collatz-Hasse-Ulam-Kakutani
Applicando l'algoritmo di Collatz a qualunque numero intero positivo, si finisce per ottenere sempre 1 (dopo un numero finito di cicli).

Nota storica.
All'inizio degli anni '30 (1930), Lothar Collatz, uno studente dell'università di Hambourg, si occupava della teoria dei numeri e della teoria dei grafi. Partiva da un numero intero positivo, gli applicava un algoritmo iterativo, tracciava i grafi associati e si poneva delle domande... che sono ancora senza risposta. Il matematico tedesco Helmut Hasse, amico di Collatz, diffuse il problema noto anche con il nome "algoritmo di Hasse" o "problema 3x+1".
Poiché Hasse presentò il problema negli anni '50 durante una visita all'università di Syracuse (vicino a New York), propose di battezzarlo "problema di Syracuse".

Il matematico polacco Stanislaw Ulam, fece circolare l'algorimo all'Università di Los Alamos, dove lavorava durante la seconda guerra mondiale. Per questo il problema è anche noto con il nome "problema di Ulam".

Negli anni '60 S. Kakutani si interessò nuovamente al problema e la congettura prese il nome di "problema di Kakutani".

Altre formulazioni del problema di Collatz

Il problema originale di Collatz
Sembra che fra le note di Collatz datate 1 luglio 1932 si trovi questo problema:

Se n è un multiplo di 3, lo si moltiplichi per 2 e si divida il risultato per 3.
Se n/3 dà come resto 1, lo si moltiplichi per 4, si tolga 1 e si divida il risultato per 3.
Se n/3 dà come resto 2, lo si moltiplichi per 4, si aggiunga 1 e si divida il risultato per 3.

La domanda è: applicando ripetutamente la funzione c(n) a partire da un numero intero positivo, la sequenza che si ottiene diverge?, converge su un numero? diventa ciclica?

Si verifica facilmente che per gli interi 1,2,3,4,5,6,7 e 9 le sequenze entrano in un ciclo del tipo: 4,5,7,9,6.

Purtroppo non si sa ancora come va a finire la sequenza che parte dal numero 8!
Ecco i suoi primi 50 termini: 8, 11, 15, 10, 13, 17, 23, 31, 41, 55, 73, 97, 129, 86, 115, 153, 102, 68, 91, 121, 161, 215, 287, 383, 511, 681, 454, 605, 807, 538, 717, 478, 637, 849, 566, 755, 1007, 1343, 1791, 1194, 796, 1061, 1415, 1887, 1258, 1677, 1118, 1491, 994, 1325, 1767, ...

Il problema 3x+1
L'algoritmo può essere espresso come iterazione della seguente funzione.

I risultati delle iterazioni possono essere rappresentati con un grafo di questo tipo, chiamato grafo di Collatz della funzione S(n)

Risposte & riflessioni

Giovanni Macchia (soluzione inviata nel Marzo 2001)
Il problema è il cosiddetto "problema 3x +1" . E' posto nel seguente modo.

Definiamo la serie Si con elemento iniziale S0 = n, con n intero positivo

e

  • Si-1/2 se Si-1 pari

    • Si =

  • 3 Si-1 + 1 se Si-1 dispari

    • La serie si definisce convergente, se

    (1) Min (n) = lim k->¥ Min(S0, S1, ..., Sk) = 1

    Se si dimostra che Min(n) = 1 per ogni n naturale, allora si capisce perché ciclicamente si arriva a ottenere sempre il numero 1, come richiesto da Gianvittorio Righi.

    Attualmente, non è stato dimostrato per tutti i casi. Esiste solo una dimostrazione debole (molto importante peraltro) dovuta a Terras, che afferma (introducendo il concetto di stopping time) che la maggioranza degli interi positivi ha il comportamento (1). Per chi volesse approfondire l'argomento suggerirei i seguenti siti (il secondo è per palati molto raffinati... )

    http://personal.computrain.nl/eric/wondrous/#part1

    http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html

    Sito Web realizzato da Gianfranco Bo - (2003)