Congettura di Collatz

Da Wikipedia, l'enciclopedia libera.

La congettura di Collatz, conosciuta anche come congettura 3n + 1, congettura di Ulam, sequenza di Hailstone o numeri di Hailstone, è una congettura matematica tuttora irrisolta. Fu enunciata per la prima volta nel 1937 da Lothar Collatz, da cui prende il nome.

Paul Erdős disse circa questa congettura: "La matematica non è ancora pronta per problemi di questo tipo". Egli offrì 500 dollari per la sua soluzione.

Indice

1 Enunciazione del problema
2 Argomenti a favore
- 2.1 Evidenza sperimentale
- 2.2 Considerazioni probabilistiche
3 Programmi per calcolare le sequenze di Collatz
4 Ottimizzazioni
5 Collegamenti esterni

[modifica] Enunciazione del problema

La congettura riguarda il seguente algoritmo:

Si prenda un intero positivo n.
Se n è pari, si divida per due; se è dispari, si moltiplichi per 3 e si aggiunga 1.
Se n = 1, l'algoritmo termina; altrimenti si ripete dal secondo passo.

O, algebricamente:

$f(n)=\left\{\begin{matrix} n/2, & \mbox{se }n\mbox{ è pari} \\ 3n+1, & \mbox{se }n\mbox{ è dispari} \end{matrix}\right.$

È possibile formare una sequenza applicando la funzione ripetutamente prendendo come primo elemento un qualunque intero positivo e, ad ogni passaggio, applicare la funzione al risultato precedente, cioè:

$a_i = \begin{cases}n & \mbox{per } i = 0 \\ f(a_{i-1}) & \mbox{per } i > 0\end{cases}$

Per esempio, iniziando con n = 6, otteniamo la sequenza 6, 3, 10, 5, 16, 8, 4, 2, 1.

La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal valore di partenza. Più formalmente:

$\forall n \isin \mathbb{N} > 0 \ \exists i \isin \mathbb{N}: (a_0 = n \Rightarrow a_i = 1)$

La congettura risulterebbe quindi falsa se esistesse una sequenza che non contiene l'1; ciò potrebbe voler dire un ciclo che si ripete senza mai dare 1, oppure una sequenza illimitata superiormente.

A volte il problema è enunciato diversamente. La condizione di terminazione (cioè di fermarsi se n = 1) viene rimossa dalla congettura, in modo che la sequenza non termini mai. Enunciando il problema in questo modo, la congettura di Collatz diventa l'affermazione che la sequenza generata dall'algoritmo raggiunga sempre il ciclo infinito 1, 4, 2, 1, 4, 2...

Vi è un altro approccio per dimostrare la congettura, che considera di percorrere dal basso verso l'alto il grafo di Collatz. Tale grafo è definito da una "funzione inversa" di quella prima considerata:

$R(n) = \begin{cases} 2n & \mbox{se } n\equiv 0,1 \\ 2n, (2n-1)/3 & \mbox{se } n\equiv -1 \end{cases} \pmod{3}.$

Studiando il problema da questa prospettiva, il problema si definisce nel modo seguente. La congettura di Collatz si riduce alle due affermazioni:

la funzione inversa forma un albero, eccezion fatta per il ciclo 1-2;
tutti gli interi sono presenti nell'albero.

[modifica] Argomenti a favore

Nonostante la congettura non sia stata provata, la maggioranza dei matematici che se ne sono occupati pensa che la congettura sia vera. Vediamo alcuni motivi a supporto.

[modifica] Evidenza sperimentale

La congettura è stata verificata a computer per tutti i valori fino a 3 × 2⁵³ = 27,021,597,764,222,976. Intuitivamente, sarebbe sorprendente se il più piccolo controesempio fosse così grande da superare questo numero. Con l'aumento della velocità dei computer, verranno controllati valori sempre più alti (pur ricordando che questi test non potranno mai dimostrare la correttezza della congettura, ma solo l'eventuale falsità).

[modifica] Considerazioni probabilistiche

se si considerano solo i numeri dispari della sequenza generata dall'algoritmo, si può affermare che in media il successivo numero dispari dovrebbe essere pari a circa i 3/4 del precedente, fatto che suggerisce che essi, a lungo termine, decrescano fino a raggiungere 1.

[modifica] Programmi per calcolare le sequenze di Collatz

Una specifica sequenza di Collatz può essere calcolata facilmente, come mostrato dal seguente esempio in pseudocodice:

function collatz(n)
  while n > 1
    show n
    if n dispari
      set n to 3n + 1
    else
      set n to n / 2
  show n

Oppure, sfruttando la ricorsione:

function collatz(n)
  show n
  if n > 1
    if n dispari
      collatz(3n + 1)
    else
      collatz(n / 2)

Questi programmi terminano quando la sequenza arriva ad 1, per evitare di stampare un ciclo infinito di 4, 2, 1. Se la congettura di Collatz è vera, i programmi terminano sempre, qualunque sia l'intero positivo di partenza (vedi problema dell'arresto).

[modifica] Ottimizzazioni

Se n è un multiplo di 4, può essere diviso per 4.

Motivo: inizialmente è pari. Diviso per due, è ancora pari, quindi può essere diviso per due una seconda volta.

Più in generale, nella fattorizzazione prima di n è possibile sostituire la potenza di due con 2⁰.

Motivo: se la potenza di 2 nella fattorizzazione prima è maggiore di 0, allora il numero è pari, ed al punto successivo si avrà la stessa fattorizzazione con 2 elevato ad una potenza inferiore di uno. Ripetendo l'operazione, si arriva a 2⁰.

Ad esempio: invece di 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (17 passi), si può calcolare 15, 46 (2¹×23), 23, 70 (2¹×35), 35, 106 (2¹×53), 53, 160 (2⁵×5), 5, 16 (2⁴), 1 (11 passi).

Se n è dispari, si può fare (3n + 1) / 2, saltando un passaggio.

Motivo: se n è dispari, 3n è pure dispari (il prodotto di due numeri dispari è sempre dispari) e 3n + 1 è pari, quindi può essere diviso per due.

Ad esempio: 3 × 35 + 1 = 106

3m + 1 fa sempre parte della della sequenza di 4m + 1. Quindi, se n ≡ 1 (mod 4), n può essere convertito in (n - 1) / 4 quante volte possibile, risparmando un passaggio ogni volta. Il numero ottenuto, pari o dispari che sia, deve essere successivamente convertito in 3n + 1.

Motivo: 4m + 1 è sempre dispari, quindi diventerà 3(4m + 1) + 1 = 12m + 4 = 4(3m + 1), e può essere diviso per quattro.

Ad esempio: 405 può essere convertito come: 405 → 101 → 25 → 6 → 19. Anche la sequenza di Collatz normale contiene 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19

Quanto detto può essere usato per una nuova formulazione, equivalente alla precedente, della funzione di Collatz:

$f(n) = \begin{cases} n / 4 & \mbox{se } n \equiv 0 \\ 3 g(n)+1 & \mbox{se } n \equiv 1 \\ n / 2 & \mbox{se } n \equiv 2 \\ \frac{1}{2}(3n+1) & \mbox{se } n \equiv 3 \end{cases} \pmod{4}$

$g(n) = \begin{cases} n & \mbox{se } n \not\equiv 1 \\ g(\frac{n-1}{4}) & \mbox{se } n \equiv 1 \end{cases} \pmod{4}$

[modifica] Collegamenti esterni

Jeff Lagarias: The 3x + 1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23. Online all'indirizzo http://www.cecm.sfu.ca/organics/papers/lagarias/
La pagina di Wolfram's Mathworld dedicata al problema e alle sue generalizzazioni: http://mathworld.wolfram.com/CollatzProblem.html

Estratto da "http://it.wikipedia.org../../../c/o/n/Congettura_di_Collatz_8c42.html"

Categorie: Teoria dei numeri | Congetture matematiche