martedì 12 settembre 2017

L'algoritmo di Collatz (o Ulam o Hasse o Syracuse...)


Nel 1930 il matematico tedesco Lothar Collatz formulò una congettura ancora oggi non dimostrata su un algoritmo che attribuisce al numero 1 una proprietà unica. 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" o anche "problema 3x+1", ma il matematico polacco Stanislaw Ulam fece circolare l'algorimo all'Università di Los Alamos, dove lavorava durante la seconda guerra mondiale, e perciò assunse anche il nome di "problema di Ulam".
Ai più è noto semplicemente come "algoritmo di Collatz".  
Questo algoritmo consiste in tre semplici regole che permettono di arrivare al numero 1 partendo da qualsiasi numero:
- se il numero è pari, si divide per 2;
- se il numero è dispari, si moltiplica per 3 e si aggiunge 1;
- si ripete il processo fino ad ottenere 1.

Facciamo un esempio, considerando il numero 13. È dispari, per cui lo moltiplichiamo per 3 ed aggiungiamo 1, ottenendo 40. Essendo pari, lo dividiamo per 2 tre volte consecutive, fino ad arrivare a 5. Moltiplichiamo 5 per 3 e aggiungiamo 1, ottenendo 16, che dividiamo quattro volte per 2 fino ad arrivare ad 1.
Si tratta di una congettura perché ancora non è stata trovata una dimostrazione per questo algoritmo, ma il fascino e l'eleganza della sua semplicità spinsero il geniale matematico Paul Erdős ad offrire 500 dollari per stimolare la risoluzione di questo problema.

Nessun commento:

Posta un commento

Lascia un commento su questo post: