Congettura di Collatz

Spread the love

È 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, un matematico ungherese, a proposito della congettura di Collatz

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

Paul Erdős

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}.

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

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

Successione per x_1= 103

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.