Conjectura de Collatz

De Viquipèdia
Dreceres ràpides: navegació, cerca

La Conjectura de Collatz és una conjectura matemàtica així denominada perquè la va proposar per primer cop el matemàtic alemany Lothar Collatz l'any 1937. La conjectura ha rebut altres noms com conjectura 3n + 1 (pel motiu que ja es veurà), conjectura d'Ulam (pel matemàtic polonès que la va estudiar, Stanisław Ulam), problema de Siracusa (per la Universitat americana de Syracusa que hi va dedicar molts esforços), algoritme de Hasse (pel matemàtic alemany Helmut Hasse), conjectura de Kakutani (pel matemàtic japonès Shizuo Kakutani), etc.

Plantejament[modifica | modifica el codi]

Considerem la següent operació sobre qualsevol nombre natural arbitrari:

  • Si el nombre és parell, el dividim per dos.
  • Si el nombre és senar, el tripliquem i li afegim una unitat.

En la notació pròpia de l'aritmètica modular, definim la funció f de la següent manera:

 f(n) = \begin{cases} n/2 &\text{si } n \equiv 0 \pmod{2}\\ 3n+1 & \text{si } n\equiv 1 \pmod{2} \end{cases}

Ara podem formar una seqüència d'enters computant aquesta operació repetidament, començant en qualsevol nombre natural i prenent el resultat de cada pas com a origen del pas següent.

En notació matemàtica::

 a_i = \begin{cases}n & \text{per } i = 0 \\ f(a_{i-1}) & \text{per } i > 0. \end{cases}

(és a dir:: a_i és el valor de f aplicat a n recursivament i vegades; a_i = f^i(n)).

La conjectura diu que aquest procés arribarà a obtenir el valor 1, independentment del nombre natural que escollim inicialment.

El i més petit tal que a_i+1 = 1 es denomina temps total de finalitazció de n.[1] La conjectura, doncs, afirma que qualsevol n té un temps total de finalització definit. Si, per algun n, no existís un i que fes que la seqüència arribi a la unitat, diríem que aquest n té un temps total de finalització infinit i la conjectura seria falsa.

Si la conjectura fos falsa, només podria ser perquè existeix algun nombre inicial que proporciona una seqüència que no conté la unitat. Una tal seqüència, o entraria en un bucle que no conté la unitat o seria creixent sense límit. No s'ha trobat cap seqüència amb aquestes propietats.

També se sap que, si existís una solució diferent de (n,m ∈ ℕ) = (2,1) per a l'equació 2^m =3^n + 1, aleshores la conjectura seria falsa; però tampoc s'han trobat solucions diferents a l'esmentada per aquesta equació.[2]

Exemples[modifica | modifica el codi]

És fàcil comprovar que quan la seqüència arriba al valor unitari, la funció entra en un bucle en el que el càlcul reiterat donaria constantment el resultat  \{4,2,1,4,2,1,4,2,1,...\} .

  • 1 és senar, per tant el següent nombre seria (3 * 1) + 1 = 4;
  • 4 és parell, per tant el següent nombre seria 4 / 2 = 2;
  • 2 és parell, per tant el següent nombre seria 2 / 2 = 1; i tornem a reiniciar el bucle.

En els càlculs fets, s'ha comprovat que fins a n = 5.764 * 10^{18} la conjectura es verifica.[3] Però també s'ha comprovat que el temps total de finalització difereix notablement d'uns nombres a altres.

Amb nombres petits, es pot veure que les seqüències segueixen camins molt diferents per nombres que són molt propers. Per exemple:

  • la seqüència del 30 és
{15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1}, després de 18 iteracions i arribant a un màxim de 160.
  • mentre que la del 31 és
{94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700, 350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283, 850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734, 1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122, 61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1}, després de 106 iteracions i arribant a un màxim de 9232.
  • al 32 (una potència de 2), només li calen 5 iteracions i el seu màxim és 32 (el seu valor inicial).

Referències[modifica | modifica el codi]

  1. Lagarias (1985), pags. 3-23.
  2. Gasull, pàgina 94.
  3. Lagarias (2011), pàgina xi.

Bibliografia[modifica | modifica el codi]