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.

Enunciazione del problema[modifica | modifica sorgente]

La congettura riguarda il seguente algoritmo:

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

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 definire la congettura, approccio 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, (n-1)/3 & \mbox{se } n\equiv 4 \pmod{6} \\ 2n & \mbox{altrimenti} \end{cases}

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-4;
  • tutti gli interi sono presenti nell'albero.

Argomenti a favore[modifica | modifica sorgente]

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.

Evidenza sperimentale[modifica | modifica sorgente]

La congettura è stata verificata a computer per tutti i valori fino a 20\times 2^{58}\approx 5{,}764\times 10^{18}.[1] 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à).

Considerazioni probabilistiche[modifica | modifica sorgente]

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.

Programmi per calcolare le sequenze di Collatz[modifica | modifica sorgente]

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.

Ottimizzazioni[modifica | modifica sorgente]

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 20=1.

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 20.
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 (21×23), 23, 70 (21×35), 35, 106 (21×53), 53, 160 (25×5), 5, 16 (24), 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 sequenza di 4m + 1. Quindi, se n ≡ 1 (mod 4), n può essere convertito in (n - 1) / 4 quante volte possibile, risparmiando 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}

Note[modifica | modifica sorgente]

  1. ^ 3x+1 conjecture verification results

Collegamenti esterni[modifica | modifica sorgente]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica