Matematica: la congettura di Collatz

È una congettura, cioè una proprietà che si presume vera ma non si è in grado di dimostrarlo rigorosamente. Le congetture affascinano perché funzionano per tutti i tentativi che si fanno per verificarla e la loro non dimostrabilità le avvolge di mistero.

In generale non è dimostrato che non si possono dimostrare ma come disse Paul Erdős, matematico ungherese, a proposito della congettura di Collatz

“La matematica non è ancora pronta per risolvere problemi del genere”

Paul Erdős

La congettura

La congettura di Collatz afferma che la successione così definita:

	x_{n+1} = 
	\begin{cases}
	3x_n + 1, & x_n \mod 2 = 0 \\
	x_n/2 & x_n \mod 2 = 1
	\end{cases}

converge sempre a 1 per n \ge N \in \mathbb{N} . Ricordo che x_n \mod 2 = 0 vuol dire che x_n è pari e x_n \mod 2 = 1 vuol dire che x_n è dispari.

Python: la libreria matplotib

Ora per divertirmi un po’ a vedere come funziona questa successione ho utilizzato Python e la libreria matplotlib che avevo già utilizzato per lo studio dell’apprendimento delle reti neurali.

È semplice installarla come libreria stand-alone per Python 3:

$ git clone git@github.com:matplotlib/matplotlib.git
$ cd matplotlib/
$ python3 setup.py install

Sorgente Python

Dopodiché la uso in un programma che semplicemente calcola la successione e la visualizzaz u un grafico

!/usr/bin/python3
import matplotlib.pyplot as plt

a = input("Dimmi un numero: ")
print("Successione di Collatz a partire da a=",a)
z = int(a)
s = []
s.append(z)

while (z != 1):
   print(z,", ")
   if (z % 2 == 0):
      z /= 2
   else:
      z = 3*z + 1
      
   s.append(z)
# la congettura d Collatz afferma che si esce sempre dal ciclo

# disegna
x = range(len(s))
plt.plot(x, s, label="Successione di Collatz")
plt.xlabel('iterazioni')
plt.ylabel('successione')
plt.title('Congettura di Collatz')
plt.legend() 
plt.grid(True)
plt.show()

Ci si può divertire a vedere il comportamento di questa succcessione che sembra davvero imprevedibile per numeri che non fanno parte della successsione delle potenze di 2. Ad esempio il 103 genera questo andamento