Corsi on-line

La congettura di Collatz in PHP

Volevo presentarvi oggi un “giochino” matematico trovato su un rivista tempo fa. I matematici mi perdonino l’espressione “giochino” col quale mi permetto di definire una serissima congettura matematica nota come la congettura di Collatz (o sequenza di Hailstone).

Il meccanismo è questo: si prenda un numero intero qualsiasi. Se il numero è pari lo divido per due, se è dispari lo moltiplico per tre e sommo uno. Il numero ottenuto se pari lo divido ancora per due e se dispari lo moltiplico per tre e aggiungo uno e così via.
Qualcuno di voi penserà (sbagliando) che la seuqenza così descritta non troverà mai una fine. In realtà non è così in quanto, dopo una serie più o meno lunga di passaggi, il risultato che otterremo sarà sempre lo stesso: uno.
Raggiunta l’unità, quindi, il ciclo si arresta.

Vediamo il codice PHP che simula la congettura di Collatz:

<?php
$n = 2131; // un numero intero maggiore di zero

while($n > 1){
  if($n % 2 != 0){ 
    $n = $n*3 + 1;
  }else{
    $n = $n/2;
  }
  echo $n . '<br/>';
}
?>

Se qualcuno volesse impazzire, o suicidarsi (un matematico l’ha fatto), provi a cercare la dimostrazione del fenomeno. Per quel che ne sò, nessuno c’è ancora riuscito.

Attualmente l’unica pseudo-dimostrazione si è ottenuta utilizzando elaboratori estremamente potenti ed utilizzando numeri interi “mostruosamente” grandi (con php, che lavora a 32 bit, il valore massimo e circa 2 miliardi) giungendo sempre allo stesso risultato: l’uno!

Due particolari:

  • il numero dei passaggi per giungere all’unità non dipende necessariamente dalla grandezza del numero di partenza;
  • ad un certo punto il calcolo porta ad un valore che è una potenza di 2 (chissà perchè), a quel punto la sequenza si trasforma in una “discesa in picchiata” verso il valore 1;
Post correlati
  • A quando una classe sul teorema di Goodstein?

  • Se vuoi che qualche blogghista, provando la classe, mi mandi a quel pase, posso anche provarci.
    Tieni presente che gia a partire dal numero 4, presupponendo di riuscire a fare un’iterazione ogni 0,000001 secondi, per avere la sequenza del numero 4 il computer sarebbe occupato per 3x10E12120694 ANNI circa.
    Questo se ho capito bene e non ho sbagliato i calcoli

I più letti del mese
Tematiche