miniatura|Graf dirigit que mostra les òrbites de nombres petits sota el mapa de Collatz, saltant els nombres parells. La conjectura de Collatz afirma que tots els camins eventualment porten cap a 1. La conjectura de Collatz és un dels problemes no resolts més famosos de les matemàtiques. La conjectura es pregunta si repetir dues operacions aritmètiques simples acabarà transformant cada nombre enter positiu en 1.
Es tracta de seqüències de nombres enters en què cada terme s'obté del terme anterior de la següent manera: si el terme anterior és parell, el terme següent és la meitat del terme anterior. Si el terme anterior és senar, el següent és 3 vegades el terme anterior més 1. La conjectura és que aquestes seqüències sempre arriben a 1, independentment del nombre enter positiu que s'esculli per iniciar la seqüència.
Aquesta conjectura porta el nom del matemàtic Lothar Collatz, que va presentar la idea l'any 1937, dos anys després de doctorar-se. També es coneix com el problema 3n + 1, la conjectura 3n + 1, la conjectura d'Ulam (per Stanisław Ulam), el problema de Kakutani (per Shizuo Kakutani), la conjectura de Thwaites (per Sir Bryan Thwaites), lalgoritme de Hasse (per Helmut Hasse), o el problema de Syracuse (per la Universitat americana de Syracuse que hi va dedicar molts esforços).Segons [Lagarias 1985, p. 4], el nom de «problema de Syracuse» va ser proposat per Hasse a la dècada del 1950, durant una visita a la Universitat de Syracuse.
La seqüència de números implicada de vegades es coneix com a seqüència de calamarsa, números de calamarsa o númerals de calamarsa (perquè els valors solen estar subjectes a múltiples baixades i ascensos com la calamarsa en un núvol),L'explicació d'aquests salts, quan es produeixen números de calamarsa, rau en el nombre de factors primers igual a 2 quan descomponem aquest nombre, que determina quantes vegades, successivament, s'aplicarà la conjectura dels nombres parells f(x)=x/2. Per exemple, la potència enèsima de 2 (2n) arribarà a 1 en n passos, la qual cosa demostra que l'abast de la conjectura de Collatz és infinit. o com a nombres meravellosos.
Paul Erdős va dir sobre la conjectura de Collatz: «Les matemàtiques potser no estan preparades per a aquests problemes». També va oferir 500 US$ per la seva solució. Jeffrey Lagarias va afirmar el 2010 que la conjectura de Collatz «és un problema extraordinàriament difícil, completament fora de l'abast de les matemàtiques actuals».
Enunciat del problema Considerem la següent operació sobre un nombre enter positiu arbitrari: Si el nombre és parell, dividir-lo per dos. Si el nombre és senar, triplicar-lo i afegeix-ne un.
En notació aritmètica modular, definim la funció ƒ de la següent manera:
Ara formem una seqüència realitzant aquesta operació repetidament, començant per qualsevol nombre enter positiu i prenent el resultat a cada pas com a entrada al següent.
En notació:
(és a dir: ai és el valor de aplicat a n recursivament i vegades; ai = i (n)
La conjectura de Collatz diu: «aquest procés arribarà finalment al número 1, independentment de quin enter positiu es tria inicialment».
Si la conjectura és falsa, només pot ser perquè hi ha algun número inicial que dona lloc a una seqüència que no conté 1. Aquesta seqüència entraria en un cicle repetitiu que exclou l'1 o augmentaria sense límit. Encara no s'ha trobat aquesta seqüència.
La i més petita tal que ai < a0 s'anomena temps d'aturada de n. De la mateixa manera, el k més petit tal que ak = 1 s'anomena temps d'aturada total de n. Si un dels índexs i o k no existeix, diem que el temps d'aturada o el temps d'aturada total, respectivament, és infinit.
La conjectura de Collatz afirma que el temps total d'aturada de cada n és finit. També equival a dir que cada n ≥ 2 té un temps d'aturada finit.
Com que 3n + 1 és parell sempre que n és senar, es pot utilitzar la forma «drecera» de la funció de Collatz:
Aquesta definició produeix valors més petits per al temps d'aturada i el temps d'aturada total sense canviar la dinàmica global del procés.
Dades empíriques Per exemple, començant per n = 12 i aplicant la funció sense «drecera» s'obté la seqüència 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.
El nombre n = 19 triga més a arribar a 1: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
La seqüència per a n = 27, enumerada i representada gràficament a continuació, fa 111 passos (41 passos a través de nombres senars, en negreta), pujant fins a 9232 abans de baixar a 1). 27, 82, 41, 124, 62, 31, 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
Els nombres amb un temps d'aturada total més llarg que el de qualsevol valor inicial més petit formen una seqüència que comença amb: 1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... .
Els valors inicials el punt màxim de la trajectòria dels quals és superior al de qualsevol valor inicial més petit són els següents: 1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ...
Nombre de passos perquè n arribi a 1 són 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ...
El valor inicial que té el temps d'aturada total més gran mentre està menor que 10 és 9, que té 19 passos, menor que 100 és 97, que té 118 passos, menor que 1000 és 871, que té 178 passos, menor que 104 és 6171, que té 261 passos, menor que 105 és , que té 350 passos, menor que 106 és , que té 524 passos, menor que 107 és , que té 685 passos, menor que 108 és , que té 949 passos, menor que 10⁹ és , que té 986 passos, menor que 1010 és , que té 1132 passos, menor que 1011 és , que té 1228 passos, menor que 1012 és , que té 1348 passos. (Note: "Delay records" are total stopping time records)
Aquests números són els més baixos amb el recompte de passos indicat, però no necessàriament els únics per sota del límit donat. Per exemple, 9.780.657.631 té 1132 passos, igual que 9.780.657.630.
Els valors inicials que tenen el temps d'aturada total més petit respecte al seu nombre de dígits (en base 2) són les potències de dos, ja que 2n es redueix a la meitat n vegades per arribar a 1, i mai s'incrementa.
Visualizations
Arguments de suport Tot i que la conjectura no s'ha demostrat, la majoria dels matemàtics que han estudiat el problema creuen que la conjectura és certa perquè l'evidència experimental i els arguments heurístics els donen suport.
Evidència experimental A partir del 2020, la conjectura s'ha verificat per ordinador per a tots els valors inicials fins a 268 ≈ . Tots els valors inicials provats fins ara acaben en el cicle de repetició (4; 2; 1) del període 3.
Aquesta evidència informàtica no és suficient per demostrar que la conjectura és certa per a tots els valors inicials. Com en el cas d'algunes conjectures refutades, com la conjectura de Pólya, es podrien trobar contraexemples quan es consideren nombres molt grans.
Tanmateix, aquestes verificacions poden tenir altres implicacions. Per exemple, es poden derivar restriccions addicionals sobre el període i la forma estructural d'un cicle no trivial.
Una heurística probabilística Si només es tenen en compte els nombres senars de la seqüència generada pel procés de Collatz, llavors cada nombre senar és de mitjana de l'anterior (més precisament, la mitjana geomètrica de les proporcions dels resultats és ).[Lagarias 1985], secció "A heuristic argument". Això produeix un argument heurístic que cada seqüència de calamarsa hauria de disminuir a llarg termini, encara que això no és una evidència contra altres cicles, només contra la divergència. L'argument no és una prova perquè suposa que les seqüències de calamarsa es munten a partir d'esdeveniments probabilístics no correlacionats (s'estableix rigorosament que l'extensió de 2-àdic del procés de Collatz té dos passos de divisió per a cada pas de multiplicació per a gairebé tots els valors inicials de 2-àdic.)
Temps d'aturada Com ha demostrat Riho Terras, gairebé tots els nombres enters positius tenen un temps d'aturada finit. En altres paraules, gairebé totes les seqüències de Collatz arriben a un punt estrictament per sota del seu valor inicial. La demostració es basa en la distribució de vectors de paritat i utilitza el teorema del límit central.
El 2019, Terence Tao va millorar aquest resultat mostrant, utilitzant la densitat logarítmica, que gairebé totes les òrbites de Collatz baixen per sota de qualsevol funció determinada del punt de partida, sempre que aquesta funció divergeixi fins a l'infinit, per molt lentament que sigui. En resposta a aquest treball, Quanta Magazine va escriure que Tao «va obtenir un dels resultats més significatius sobre la conjectura de Collatz en dècades».
Límits inferiors En una proba assistida per ordinador, Krasikov i Lagarias van demostrar que el nombre de nombres enters de l'interval [1,x] que finalment arriben a 1 és almenys igual a per a tots els x prou grans.
Cicles En aquesta part, considerem la forma de drecera de la funció de Collatz
Un cicle és una seqüència de diferents nombres enters positius on , , ..., i .
L'únic cicle conegut és (1,2) del període 2, anomenat cicle trivial.
Llargada del cicle Se sap que la llargada d'un cicle no trivial és d'almenys 17.087.915. De fet, [Eliahou 1993] va demostrar que el període p de qualsevol cicle no trivial és de la forma
on , i són nombres enters no negatius, i . Aquest resultat es basa en l'expansió de la fracció contínua .
-cicles Un k-cicle és un cicle que es pot dividir en 2k subseqüències contigües: k seqüències creixents de nombres senars alternant amb k seqüències decreixents de nombres parells. Per exemple, si el cicle consisteix en una única seqüència creixent de nombres senars seguida d'una seqüència decreixent de nombres parells, s'anomena 1-cicle.
[Steiner 1977] va demostrar que no hi ha un cicle més que el trivial (1; 2). [Simons 2005] va utilitzar el mètode de Steiner per demostrar que no hi ha 2-cicles. [Simons i de Weger 2005] van ampliar aquesta demostració fins a 68-cicles; no hi ha k-cicles fins a k = 68. Per a cada k més enllà de 68, aquest mètode dona un límit superior per al terme més petit d'un k-cicle; per exemple, si hi ha un 77-cicle, almenys un element del cicle és inferior a 38137×250. Juntament amb la verificació de la conjectura fins a 268, això implica la inexistència d'un k-cicle no trivial fins a k = 77. A mesura que continuen les cerques exhaustives per ordinador, es poden descartar valors de k més grans. Per afirmar l'argument de manera més intuïtiva: no cal buscar cicles que tinguin com a màxim 77 circuits, on cada circuit consta de pujades consecutives seguits de baixades consecutives.
Altres formulacions de la conjectura A l'invers Hi ha un altre enfocament per demostrar la conjectura, que considera el mètode de baix a dalt per fer créixer l'anomenat graf de Collatz. El graf de Collatz és un graf definit per la relació inversa