La congettura di Collatz (3x + 1) pt. 2

Francesco Scolz
8 nov 2024
Tempo di lettura: 6 min

Rieccoci qua

Devo però confessare una cosa...

La scorsa volta mi sono fermato con due casi particolari che riguardano la congettura di Collatz

E non ho approfondito i casi generali perché non avevo ancora una risposta!

Ma oggi, cel'ho!

Eccola qua

- - - - - - - - -

Per chi non ha ancora visto la parte 1 consiglio vivamente di andarsela a riprendere, poiché userò concetti già spiegati e potrebbero risultare complicati da capire se non avete seguito dall'inizio

Detto questo, ritorniamo al nostro diagramma:

La scorsa volta abbiamo visto come i casi estremi (braccio destro e braccio sinistro) siano impossibili da seguire all'infinito dato x∈N

Dunque rimane un caso fondamentale da trattare per provare che la congettura è in effetti vera: il caso generale

Ovvero, tutte le combinazioni che presentano risultati sia pari sia dispari

Ad esempio: destra, sinistra, sinistra, destra, destra, sinistra...

Dividamo questo caso generale in altri 4 casi più specifici:

Il numero si alterna destra-sinistra (o sinistra-destra) con una ciclicità pari a 1 (una volta pari una volta dispari) raggiungendo un valore "finale" diverso da 1
Il numero si alterna destra-sinistra (o sinistra-destra) con una ciclicità diversa da 1, con successivi numeri pari raggiungendo un valore "finale" diverso da 1
Il numero si alterna destra-sinistra (o sinistra-destra) con una ciclicità diversa da 1, con successivi numeri dispari raggiungendo un valore "finale" diverso da 1
Il numero si alterna destra-sinistra (o sinistra-destra) senza alcuna ciclicità

Sembra più complicato di quello che è veramente, fidatevi!

E come l'altra volta, partiamo dal caso 1, il più semplice:

A1 = x

A2 = ( 3x + 1 ) / 2

A3 = ( ( 3x + 1 ) / 2 ) / 2 = ( 3x + 1 ) / 4

A4 = ( 3 ( ( 3x + 1 ) / 4 ) + 1 ) / 2

...

Riscriviamo dunque le equazioni in questo modo, come la scorsa volta:

A1 = x

A2 = ( A1 ) / 2

A3 = A2 / 2

A4 = ( 3 ( A3 ) + 1 ) / 2

...

Per uguaglianze

Dunque, generalizziamo i casi:

A[n] =

se n = 2k (pari): A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

se n = 2k + 1 (dispari): A[n] = A[n-1] / 2

( k∈N )

Possiamo pensare questa cosa come una funzione composta ( equazioni diverse per diversi domini )

Risolvendo per A[∞]: (quando l'algoritmo non finisce mai nel ciclo 4-2-1)

{ A[∞] = ( 3 ( A[∞] ) + 1 ) / 2

{ A[∞] = A[∞] / 2

{ A[∞] = - 1

(salto direttamente ai risultati)

{ A[∞] = 0

E come sappiamo, -1 e 0 non soddisfano la condizione di partenza x∈N

(poiché l'algoritmo in questione, partendo da numeri naturali, non può restituire valori non naturali. È dimostrabile)

Otterremmo risultati non accettabili anche se fossimo partiti con una x pari (A2 = A1 / 2), e quindi per i prossimi casi sottointenderò questa proprietà**

Passiamo dunque a trattare il secondo caso:

Proviamo con una ciclicità 2 (due volte pari, una dispari)

A1 = x

A2 = ( 3x + 1 ) / 2

A3 = ( ( 3x + 1 ) / 2 ) / 2 = ( 3x + 1 ) / 4

A4 = ( ( 3x + 1 ) / 4 ) / 2 = ( 3x + 1 ) / 8

A5 = ( 3 ( ( 3x + 1 ) / 8 ) + 1 ) / 2

...

Ancora, possiamo generalizzare:

A[n] =

se n = 1 + 4k (1, 5, 9, 13...): A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

( ∀n ≠ 1 + 4k ) (2, 3, 4, 6...): A[n] = A[n-1] / 2

( k∈N )

{ A[∞] = ( 3 ( A[∞] ) + 1 ) / 2

{ A[∞] = A[∞] / 2

Le stesse equazioni di prima! Dunque

{ A[∞] = - 1

{ A[∞] = 0

Non accettabili

Risolviamo ora il caso 2 con una ciclicità 3 ( pari - pari- pari - dispari ):

A1 = x

A2 = ( 3x + 1 ) / 2

A3 = ( ( 3x + 1 ) / 2 ) / 2 = ( 3x + 1 ) / 4

A4 = ( ( 3x + 1 ) / 4 ) / 2 = ( 3x + 1 ) / 8

A5 = ( ( 3x + 1 ) / 8 ) / 2 = ( 3x + 1 ) / 16

A6 = ( 3 ( ( 3x + 1 ) / 16 ) + 1 ) / 2

...

Generalizziamo:

A[n] =

se n = 1 + 5k (1, 6, 11...): A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

( ∀n ≠ 1 + 5k ) (2, 3, 4, 5, 7...): A[n] = A[n-1] / 2

( k∈N )

{ A[∞] = ( 3 ( A[∞] ) + 1 ) / 2

{ A[∞] = A[∞] / 2

{ A[∞] = - 1

{ A[∞] = 0

Ora, se generalizziamo anche per la ciclicità:

A1 = x

A2 = ( 3x + 1 ) / 2

A3 = ( 3x + 1 ) / 4

....

A[n] = ( ( 3x + 1 ) / b ) / 2 = ( 3x + 1 ) / 2b

A[n+1] = ( 3 ( ( 3x + 1 ) / 2b ) + 1 ) / 2

A[n+2] = ( 3 ( ( 3x + 1 ) / 2b ) + 1 ) / 4

...

A[n] =

se n = 1 + (c+2)k: A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

( ∀n ≠ 1 + (c+2)k ): A[n] = A[n-1] / 2

( k,c∈N , c = ciclicità)

E, come sempre, le soluzioni risultano -1 e 0, non accettabili per questo problema

Quindi, anche questo caso è impossibile per numeri naturali

Caso 3:

Questo è il caso in cui ci sono successioni di destra-sinistra con dispari consecutivi

Generalizziamo subito per la ciclicità, senza ripetere i passaggi:

A1 = x

A2 = ( 3x + 1 ) / 2

A3 = ( 3 ( ( 3x + 1 ) / 2 ) + 1 ) / 2

...

A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

A[n+1] = A[n] / 2

A[n+2] = ( 3 ( A[n+1] ) + 1 ) / 2

...

Generalizziamo sostituendo quello che possiamo:

A1 = x

A2 = ( 3 ( A1 ) + 1 ) / 2

A3 = ( 3 ( A2 ) + 1 ) / 2

...

A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

A[n+1] = A[n] / 2

A[n+2] = ( 3 ( A[n+1] ) + 1 ) / 2

...

E generalizziamo in una sola formula:

A[n] =

se n = 1 + (c+2)k: A[n] = ( A[n-1] ) / 2

( ∀n ≠ 1 + (c+2)k ): A[n] = ( 3 ( A[n-1] ) + 1 ) / 2

( k,c∈N , c = ciclicità)

E come vediamo

Non cambia nulla dal caso 2 fuorché il fatto che ora le due equazioni sono invertite:

A / 2 per i passaggi più "rari" (A diventa pari con una minore frequenza dato che abbiamo supposto una ciclicità di dispari, la quale IMPONE che ci siano passaggi che risultano in valori dispari più frequentemente)