La congettura di Collatz

(note a cura di Roberto Bigoni)

1

Si dice che un numero c₀ genera una successione di Collatz se è il primo elemento di una sequenza C di numeri naturali c_i tali che

Se C contiene il numero 1 si termina il calcolo quando si ottiene 1, dato che da questo numero in poi la successione non uscirebbe più dal ciclo 1-4-2-1.

Tutti i termini di una stessa successione di Collatz si dicono C-equivalenti.

Per indicare che m è C-equivalente a n si scrive .

Si congettura che ogni numero naturale sia C-equivalente ad un numero minore, cioè che da qualunque numero si inizi la successione si ottenga sempre 1.

Questa congettura, pur verificata su moltissimi numeri con programmi di calcolo simili a quello proposto nell'applet sovrastante, non è ancora stata dimostrata in modo generale, cioè valida formalmente per ogni numero naturale.

Per una informazione generale sugli studi su questo argomento, vedere:

• MathWorld.
• Wikipedia

Questa esposizione intende dimostrare che la dimostrazione della congettura è impossibile.

A questo scopo si analizzano in particolare le successioni generate dai numeri dispari della successione , concludendo che per alcune di queste successioni è impossibile escludere a priori che esse tendano all'infinito perché non si può escludere che contengano cicli in cui il valore in uscita è superiore al valore in entrata.

2.0

Tutti i numeri pari sono C-equivalenti alla loro metà, quindi sono C-equivalenti ad un numero minore.

2.1

I numeri dispari possono essere ripartiti nelle due successioni di termini

2.2

Tutti i numeri della successione

sono C-equivalenti a , quindi sono C-equivalenti ad un numero minore.

Infatti

3

I numeri dispari rimanenti sono quelli della successione

per i quali si ha

Quindi questi numeri sono C-equivalenti ad un numero maggiore.

4

La successione s_i può essere ripartita in quattro successioni:

4.0

I numeri s_0,i sono

Per i numeri s_0,i si ha

quindi questi s_i sono C-equivalenti ad un numero minore.

4.1

I numeri s_1,i sono

Per i numeri s_1,i si ha

Si ottiene un numero della successione d_i, quindi

4.1.0

Se i è dispari, l'ultimo numero ottenuto è pari e dimezzandolo si ottiene un numero minore di quello iniziale.

4.1.1

Altrimenti l'ultimo numero ottenuto è maggiore del numero iniziale. Questo numero appartiene alla sottosuccessione

Gli elementi di questa successione appartengono alternamente alle successioni d_i e s_i.

Quelli che appartengono alla s_i sono del tipo

e si distribuiscono uniformemente in tutte le quattro sottosuccessioni s_j,i del punto 4.

Non si può escludere che elementi di questa successione generino dei cicli infiniti di numeri sempre maggiori.

4.2

I numeri s_2,i sono

Questa successione può, a sua volta, essere ripartita in due successioni

4.2.0

I numeri s_2,0,i sono

Per questi numeri si ha

Questo è un numero della successione d_i. Infatti

Questo numero è equivalente a

cioè ad un numero minore.

4.2.1

I numeri s_2,1,i sono

Per questi numeri si ha

Questo è un numero della successione d_i, quindi

I numeri sono tutti appartenenti alla successione s_i. Infatti

Questi numeri

si distribuiscono uniformemente in tutte le quattro sottosuccessioni s_j,i del punto 4.

Non si può escludere che elementi di questa successione generino dei cicli infiniti di numeri sempre maggiori.

4.3

I numeri s_3,i sono

Per questi numeri si ha

I numeri ottenuti sono maggiori del numero iniziale e appartengono alla successione s_i. Infatti

Questi numeri

si distribuiscono uniformemente in tutte le quattro sottosuccessioni s_j,i del punto 4.

Non si può escludere che elementi di questa successione generino dei cicli infiniti di numeri sempre maggiori.

5

I risultati ottenuti nei punti 4.1.1, 4.2.1 e 4.3 mostrano che che è impossibile escludere che esistano elementi della successione s_i che generino successioni di Collatz divergenti.