Mostra la font per a Conjectura de Collatz

[[Fitxer:Collatz-graph-50-no27.svg|miniatura|[[Graf dirigit]] que mostra les [[Órbita (dinàmica)|ò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]] [[Nombre positiu|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 [[Nombre parell|parell]], el terme següent és la meitat del terme anterior. Si el terme anterior és [[Nombre senar|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 [[Doctorat|doctorar-se]].{{sfn|O'Connor|2006}} 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 [[Bryan Thwaites|Sir Bryan Thwaites]]), l{{'}}'''algoritme de Hasse''' (per [[Helmut Hasse]]), o '''el problema de Syracuse''' (per la [[Universitat de Syracuse|Universitat americana de Syracuse]] que hi va dedicar molts esforços).<ref group="Nota">Segons ''[Lagarias 1985, p. 4]'', el nom de ''«problema de Syracuse»'' va ser proposat per [[Helmut Hasse|Hasse]] a la dècada del 1950, durant una visita a la [[Universitat de Syracuse]].</ref>{{sfn|Maddux|Johnson|1997|p=160}}

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]]),<ref group="Nota">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 (2<sup>n</sup>) arribarà a 1 en ''n'' passos, la qual cosa demostra que l'abast de la conjectura de Collatz és infinit.</ref>{{sfn|Pickover|2001|p=116-118}}<ref name="hn">{{ref-web |títol=Hailstone Number |url=http://mathworld.wolfram.com/HailstoneNumber.html |obra=[[MathWorld]] |editor=Wolfram Research |llengua=anglès}}</ref> o com a '''nombres meravellosos'''.{{sfn|Hofstadter|1979|p=400-402}}

[[Paul Erdős]] va dir sobre la conjectura de Collatz: ''«Les matemàtiques potser no estan preparades per a aquests problemes»''.{{sfn|Guy|2004|p=330-336}} També va oferir 500 [[Dòlar dels Estats Units|US$]] per la seva solució.{{sfn|Guy|1983|p=35-41}} 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»''.{{sfn|Lagarias|2011}}

== Enunciat del problema ==
Considerem la següent operació sobre un [[nombre enter]] [[Nombre positiu|positiu]] arbitrari:
* Si el nombre és [[Nombre parell|parell]], dividir-lo per dos.
* Si el nombre és [[Nombre senar|senar]], triplicar-lo i afegeix-ne un.

En notació [[aritmètica modular]], definim la [[funció]] ''ƒ'' de la següent manera:

::<math> f(n) = \begin{cases} \frac{n}{2} &\text{si } n \equiv 0 \pmod{2}\\[4px] 3n+1 & \text{si } n\equiv 1 \pmod{2} .\end{cases}</math>

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ó:

::<math> a_i = \begin{cases}n & \text{per a } i = 0 \\ f(a_{i-1}) & \text{per a } i > 0 \end{cases}</math>

(és a dir: ''a<sub>i</sub>'' és el valor de ''{{mvar|ƒ}}'' aplicat a ''n'' [[Recursivitat|recursivament]] ''i'' vegades; ''a<sub>i</sub>'' = ''{{mvar|ƒ}}<sup>i</sup>'' (''n'')

La conjectura de Collatz diu: ''«aquest procés arribarà finalment al número 1, independentment de quin enter positiu es tria inicialment»''.

<gallery mode="packed" heights="300">
Fitxer:Collatz-stopping-time.svg|Nombres de l'1 al 9999 i el seu corresponent temps total d'aturada
Fitxer:Collatz Gif.gif|Temps total d'aturada dels números fins a 250, 1.000, 4.000, 20.000, 100.000, 500.000
</gallery>

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.

<gallery mode="packed" heights="300">
Fitxer:Collatz-10Million.png|Temps d'iteració per a les entrades de 2 fins a 10<sup>7</sup>
Fitxer:Collatz Conjecture 100M.jpg||Temps d'iteració per a les entrades de 2 fins a 10<sup>8</sup>
</gallery>

La ''i'' més petita tal que ''a<sub>i</sub> < a<sub>0</sub>'' s'anomena ''temps d'aturada de n''. De la mateixa manera, el ''k'' més petit tal que ''a<sub>k</sub> = 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.

<gallery mode="packed" heights="200">
Fitxer:CollatzStatistic100million.png|[[Histograma]] dels temps totals d'aturada per als números de l'1 al 10<sup>8</sup>. El temps total d'aturada es troba a l'eix ''x'', la freqüència a l'eix ''y''
Fitxer:CollatzStatistic1billion.png|Histograma dels temps totals d'aturada per als números de l'1 al 10⁹. El temps total d'aturada es troba a l'eix ''x'', la freqüència a l'eix ''y''
</gallery>

Com que ''3n + 1'' és parell sempre que ''n'' és senar, es pot utilitzar la forma ''«drecera»'' de la funció de Collatz:

::<math> f(n) = \begin{cases} \frac{n}{2} &\text{si } n \equiv 0 \pmod{2},\\[4px] \frac{3n+1}{2} & \text{si } n\equiv 1 \pmod{2}. \end{cases}</math>

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ó {{mvar|ƒ}} 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''' {{OEIS|id=A008884}}

<gallery mode="packed" heights="300">
Fitxer:Collatz5.svg
</gallery>

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, ... {{OEIS|id=A006877}}.

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, ... {{OEIS|id=A006884}}

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, ... {{OEIS|id=A006577}}

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 10<sup>4</sup> és 6171, que té 261 passos,
:menor que 10<sup>5</sup> és {{val|77031}}, que té 350 passos,
:menor que 10<sup>6</sup> és {{val|837799}}, que té 524 passos,
:menor que 10<sup>7</sup> és {{val|8400511}}, que té 685 passos,
:menor que 10<sup>8</sup> és {{val|63728127}}, que té 949 passos,
:menor que 10⁹ és {{val|670617279}}, que té 986 passos,
:menor que 10<sup>10</sup> és {{val|9780657630}}, que té 1132 passos,{{sfn|Leavens|Vermeulen|1992|p=79-99}}
:menor que 10<sup>11</sup> és {{val|75128138247}}, que té 1228 passos,
:menor que 10<sup>12</sup> és {{val|989345275647}}, que té 1348 passos.<ref name=Roosendaal>{{ref-web |cognom=Roosendaal |nom=Eric |títol=3x+1 delay records |url=http://www.ericr.nl/wondrous/delrecs.html}} (Note: "Delay records" are total stopping time records)</ref>

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 [[Sistema binari|base 2]]) són les [[Potència de dos|potències de dos]], ja que 2<sup>n</sup> es redueix a la meitat ''n'' vegades per arribar a 1, i mai s'incrementa.

== Visualizations ==
<gallery mode="packed" heights="300">
Fitxer:Collatz orbits of the all integers up to 1000.svg|Graf dirigit que mostra les òrbites dels primers 1000 nombres
Fitxer:CollatzConjectureGraphMaxValues.jpg|L'eix {{mvar|x}} representa el nombre inicial, l'eix {{mvar|y}} representa el nombre més alt assolit durant la cadena fins a 1. Aquest gràfic mostra un eix {{mvar|y}} restringit: alguns valors {{mvar|x}} produeixen intermedis fins a {{val|2.7e7}} (per a {{math|''x'' {{=}} 9663}})
Fitxer:Collatz-max.png|El mateix gràfic a l'esquerra però a escala logarítmica, de manera que es mostren tots els valors ''y''. La primera línia gruixuda cap a la meitat de la parcel·la correspon a la punta a 27, que arriba al màxim a 4616
Fitxer:All Collatz sequences of a length inferior to 20.svg|L'arbre de tots els nombres que tenen menys de 20 passos.
</gallery>

== 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ística|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 2<sup>68</sup> ≈ {{val|2.95e20}}. Tots els valors inicials provats fins ara acaben en el cicle de repetició (4; 2; 1) del període 3.{{sfn|Barina|2020|2681-2688}}

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 [[Contraexemple|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.{{sfn|Garner|1981|p=19-22}}{{sfn|Eliahou|1993|p=45-56}}{{sfn|Simons|de Weger|2005|p=51-70}}

=== 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 {{sfrac|3|4}} de l'anterior (més precisament, la [[mitjana geomètrica]] de les proporcions dels resultats és {{sfrac|3|4}}).<ref group="Nota">''[Lagarias 1985]'', secció "[http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/node3.html A heuristic argument"].</ref> 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 [[Nombre p-àdic|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 [[Nombre enter|nombres enters]] [[Nombre positiu|positius]] tenen un temps d'aturada finit.{{sfn|Terras|1976|p=241-252}} 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 [[Funció de densitat de probabilitat|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»''.<ref name="Tao">{{ref-web |cognom=Tao |nom=Terence |títol=Almost all Collatz orbits attain almost bounded values |url=https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/ |obra=What's new |data=10 de setembre de 2019 |llengua=anglès}}</ref><ref name="Quanta">{{ref-publicació |cognom=Hartnett |nom=Kevin |article=Mathematician Proves Huge Result on 'Dangerous' Problem |url=https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/ |publicació=Quanta Magazine |llengua=anglès}}</ref>

=== 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 {{math|''x''<sup>0.84</sup>}} per a tots els ''x'' prou grans.{{sfn|Krasikov|Lagarias|2003|p=237-258}}

== Cicles ==
En aquesta part, considerem la forma de drecera de la funció de Collatz

::<math> f(n) = \begin{cases} \frac{n}{2} &\text{si } n \equiv 0 \pmod{2},\\[4px] \frac{3n+1}{2} & \text{si } n \equiv 1 \pmod{2}. \end{cases}</math>

Un [[Seqüència periòdica|cicle]] és una seqüència {{math|(''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a<sub>q</sub>'')}} de diferents nombres enters positius on {{math|''ƒ''(''a''<sub>0</sub>) {{=}} ''a''<sub>1</sub>}}, {{math|''ƒ''(''a''<sub>1</sub>) {{=}} ''a''₂}}, ..., i {{math|''ƒ''(''a<sub>q</sub>'') {{=}} ''a''<sub>0</sub>}}.

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 
::<math>p = 301994 a + 17087915 b + 85137581 c</math>
on {{mvar|a}}, {{mvar|b}} i {{mvar|c}} són nombres enters no negatius, {{math|''b'' ≥ 1}} i {{math|1=''ac'' = 0}}. Aquest resultat es basa en l'expansió de la [[fracció contínua]] {{math|{{sfrac|ln 3|ln 2}}}}.{{sfn|Eliahou|1993|p=45-56}}

=== {{mvar|k}}-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.{{sfn|Simons|de Weger|2005|p=51-70}} 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).{{sfn|Steiner|1977|p=553-559}} ''[Simons 2005]'' va utilitzar el mètode de Steiner per demostrar que no hi ha ''2''-cicles.{{sfn|Simons|2005|p=1565-1572}} ''[Simons i de Weger 2005]'' van ampliar aquesta demostració fins a ''68''-cicles; no hi ha ''k''-cicles fins a ''k'' = 68.{{sfn|Simons|de Weger|2005|p=51-70}} 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×2<sup>50</sup>.{{sfn|Simons|de Weger|2005|p=51-70}} Juntament amb la verificació de la conjectura fins a 2<sup>68</sup>, això implica la inexistència d'un ''k''-cicle no trivial fins a ''k'' = 77.{{sfn|Barina|2020|2681-2688}} 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 (matemàtiques)|graf]] definit per la relació inversa

<math> R(n) = \begin{cases} \{2n\} & \text{si } n\equiv 0,1,2,3,5 \\[4px] \left\{2n,\frac{n-1}{3}\right\} & \text{si } n\equiv 4 \end{cases} \pmod 6. </math>

<gallery mode="packed" heights="200">
Fitxer:Collatz-tree, depth=20.svg|Els primers 21 nivells del graf de Collatz generats de manera ascendent. El graf inclou tots els números amb una longitud d'òrbita de 21 o menys
</gallery>

Per tant, en comptes de demostrar que tots els nombres enters positius eventualment condueixen a 1, podem provar de demostrar que 1 condueix cap enrere a tots els enters positius. Per a qualsevol nombre enter ''n'', ''n ≡ 1 (mod 2)'' [[si i només si]] ''3n + 1 ≡ 4 (mod 6)''. De manera equivalent, {{math|{{sfrac|''n'' − 1|3}} ≡ 1 (mod 2)}} si i només si ''n ≡ 4 (mod 6)''. Conjecturalment, aquesta relació inversa forma un [[Arbre (teoria de grafs)|arbre]] excepte per al [[Bucle (teoria de grafs)|bucle]] 1–2–4 (la inversa del bucle 4–2–1 de la funció inalterada ''f'' definida a la secció ''Enunciat del problema'' d'aquest article).

Quan la relació ''3n + 1'' de la funció ''ƒ'' es substitueix per la relació «drecera» substitutiva comuna {{math|{{sfrac|3''n'' + 1|2}}}}, el graf de Collatz es defineix per la relació inversa,

::<math> R(n) = \begin{cases} \{2n\} & \text{si } n\equiv 0,1 \\[4px] \left\{2n,\frac{2n-1}{3}\right\} & \text{si } n\equiv 2 \end{cases} \pmod 3. </math>

Per a qualsevol nombre enter ''n'', ''n ≡ 1 (mod 2)'' si i només si {{math|{{sfrac|3''n'' + 1|2}} ≡ 2 (mod 3)}}. De manera equivalent, {{math|{{sfrac|2''n'' − 1|3}} ≡ 1 (mod 2)}} si i només si ''n ≡ 2 (mod 3)''. Conjecturalment, aquesta relació inversa forma un arbre excepte per a un bucle 1–2 (la inversa del bucle 1–2 de la funció ''{{mvar|ƒ}}(n)'' revisada com s'ha indicat anteriorment).

Alternativament, substituïm el ''3n + 1'' per ''n''′/''H''(''n''′)  on ''n′ = 3n + 1'' i ''H''(''n''′) és la [[Potència de dos|potència de 2]] més alta que divideix ''n''′ (sense [[Residu (aritmètica)|residu]]). La funció resultant ''ƒ'' mapeja de nombres senars a nombres senars. Ara suposem que per a un nombre senar ''n'', aplicant aquesta operació ''k'' vegades, es produeix el nombre 1 (és a dir, ''{{mvar|ƒ}}<sup>k</sup>''(''n'') = 1). Aleshores, en [[Sistema binari|binari]], el nombre ''n'' es pot escriure com la [[concatenació]] de [[Cadena (informàtica)|cadenes]] {{math|''w''<sub>''k''</sub> ''w''<sub>''k''−1</sub> ... ''w''<sub>1</sub>}} on cada {{math|''w''<sub>''h''</sub>}} és un extracte finit i contigu de la representació de {{math|{{sfrac|1|3<sup>''h''</sup>}}}}.<ref name="Colussi2011">{{ref-publicació |cognom=Colussi |nom=Livio |data=9 de setembre de 2011 |article=The convergence classes of Collatz function |publicació=Theoretical Computer Science |doi=10.1016/j.tcs.2011.05.056 |volum=412(39) |pàgina=5409-5419|llengua=anglès}}</ref> Per tant, la representació de ''n'' té les repeticions de {{math|{{sfrac|1|3<sup>''h''</sup>}}}}, on cada repetició es gira opcionalment i després es replica fins a un nombre finit de [[Bit|bits]]. És només en binari que això passa.<ref name="Hew2016">{{ref-publicació |cognom=Hew |nom=Patrick Chisan |data=7 de març de 2016 |article=Working in binary protects the repetends of 1/3<sup>''h''</sup>: Comment on Colussi's 'The convergence classes of Collatz function' |publicació=Theoretical Computer Science |doi=10.1016/j.tcs.2015.12.033 |volum=618 |pàgina=135-141|llengua=anglès}}</ref> Conjecturalment, es pot arribar a totes les cadenes binàries ''s'' que acaben amb un ''1'' mitjançant una representació d'aquesta forma (on podem afegir o suprimir els ''0'' a les ''s'').

=== Com una màquina abstracta que calcula en base dos ===
Les aplicacions repetides de la funció Collatz es poden representar com una [[màquina abstracta]] que gestiona [[Cadena (informàtica)|cadenes]] de [[Bit|bits]]. La màquina realitzarà els tres passos següents sobre qualsevol nombre senar fins que només quedi un 1:
* Afegir 1 a l'extrem (dret) del nombre en binari (donant ''2n + 1'');
* Afegir-ho al nombre original per suma binària (donant ''2n + 1 + n = 3n + 1'');
* Treure tots els 0 posteriors (és a dir, dividir-los repetidament per 2 fins que el resultat sigui senar).

==== Exemple ====
El número inicial 7 s'escriu a la base dos com 111. La seqüència de Collatz resultant és:

<div style="font-family:monospace">
 111
 {{subratllat|111'''1'''}}
 1011<s>0</s>
 {{subratllat|1011'''1'''}}
 10001<s>0</s>
 {{subratllat|10001'''1'''}}
 1101<s>00</s>
 {{subratllat|1101'''1'''}}
 101<s>000</s>
 {{subratllat|101'''1'''}}
 1<s>0000</s>
</div>

=== Com a seqüència de paritat ===
Per a aquesta secció, considerem la funció de Collatz en la forma lleugerament modificada

:<math> f(n) = \begin{cases} \frac{n}{2} &\text{si } n \equiv 0 \\[4px] \frac{3n + 1}{2} & \text{si } n \equiv 1 \end{cases} \pmod{2}.</math>

Això es pot fer perquè quan ''n'' és senar, ''3n + 1'' sempre és parell.

Si P(...) és la paritat d'un nombre, és a dir, {{math|P(2''n'') {{=}} 0}} i {{math|P(2''n'' + 1) {{=}} 1}}, llavors podem definir la ''seqüència de paritat de Collatz'' (o ''vector de paritat'') per a un nombre ''n'' com {{math|''p<sub>i</sub>'' {{=}} P(''a<sub>i</sub>'')}}, on {{math|''a''<sub>0</sub> {{=}} ''n''}}, i {{math|''a''<sub>''i''+1</sub> {{=}} ''ƒ''(''a''<sub>''i''</sub>)}}.

Quina operació es realitza, {{math|{{sfrac|3''n'' + 1|2}}}} o {{math|{{sfrac|''n''|2}}}}, depèn de la paritat. La seqüència de paritat és la mateixa que la seqüència d'operacions.

Utilitzant aquesta forma per a {{math|''ƒ''(''n'')}}, es pot demostrar que les seqüències de paritat de dos nombres ''m'' i ''n'' coincidiran en els primers ''k'' termes [[si i només si]] ''m'' i ''n'' són equivalents mòdul {{math|2<sup>''k''</sup>}}. Això implica que cada nombre s'identifica de manera única per la seva seqüència de paritat i, a més, si hi ha diversos cicles de calamarsa, els seus cicles de paritat corresponents han de ser diferents.{{sfn|Terras|1976|p=241-252}}{{sfn|Lagarias|1985|p=3-23}}

L'aplicació de la funció ''ƒ'' ''k'' vegades al nombre {{math|''n'' {{=}} 2<sup>''k''</sup>''a'' + ''b''}} donarà el resultat {{math|3<sup>''c''</sup>''a'' + ''d''}}, on ''d'' és el resultat d'aplicar la funció ''ƒ'' ''k'' vegades a ''b'' i ''c'' és el nombre d'augments que s'han trobat durant aquesta seqüència. Per exemple, per a {{math|2<sup>5</sup>''a'' + 1}} hi ha 3 augments a mesura que 1 itera a 2, 1, 2, 1, i finalment a 2, de manera que el resultat és {{math|3<sup>3</sup>''a'' + 2}}; per a {{math|2<sup>2</sup>''a'' + 1}} només hi ha 1 augment quan 1 puja a 2 i baixa a 1, de manera que el resultat és {{math|3''a'' + 1}}. Quan ''b'' és {{math|2<sup>''k''</sup> − 1}}, hi haurà ''k'' augments i el resultat serà {{math|2 × 3<sup>''k''</sup>''a'' − 1}}. El factor de 3 que multiplica a és independent del valor d{{'}}''a''; només depèn del comportament de ''b''. Això permet predir que determinades formes de nombres sempre portaran a un nombre més petit després d'un cert nombre d'iteracions: per exemple, {{math|4''a'' + 1}} es converteix en {{math|3''a'' + 1}} després de dues aplicacions de ''ƒ'' i {{math|16''a'' + 3}} es converteix en {{math|9''a'' + 2}} després de 4 aplicacions de ''{{mvar|ƒ}}''. Però que aquests nombres més petits continuïn fins a 1 depèn del valor de ''a''.

=== Com a sistema d'etiquetes ===
Per a la funció de Collatz en la forma

::<math> f(n) = \begin{cases} \frac{n}{2} &\text{si } n \equiv 0 \\[4px] \frac{3n+1}{2} & \text{si } n \equiv 1. \end{cases} \pmod{2}</math>

Les seqüències de calamarsa es poden calcular mitjançant el sistema extremadament senzill de [[Màquina de Post|2-etiquetes]] amb regles de producció

::{{math|''a'' → ''bc''}}, {{math|''b'' → ''a''}}, {{math|''c'' → ''aaa''}}.

En aquest sistema, l'enter positiu ''n'' es representa amb una cadena de ''n'' còpies de ''a'', i la iteració de l'operació d'etiqueta s'atura en qualsevol paraula de longitud inferior a 2. (Adaptat de ''[De Mol 2008]'').

<pre>
2-tag system 
 Alphabet: {a,b,c} 
 Production rules:
 a --> bc
 b --> a
 c --> aaa

Computation
 Initial word: aaa <--> n=3
 abc 
 cbc
 caaa
 aaaaa <--> 5
 aaabc
 abcbc
 cbcbc
 cbcaaa
 caaaaaa
 aaaaaaaa <--> 8
 aaaaaabc
 aaaabcbc
 aabcbcbc
 bcbcbcbc
 bcbcbca
 bcbcaa
 bcaaa
 aaaa <--> 4
 aabc
 bcbc
 bca
 aa <--> 2
 bc
 a <--> 1
 (halt)
</pre>

La conjectura de Collatz afirma de manera equivalent que aquest sistema d'etiquetes, amb una cadena finita arbitrària de ''a'' com a paraula inicial, finalment s'atura.

== Ampliacions a dominis més grans ==
=== Iteració sobre tots els nombres enters ===
Una extensió de la conjectura de Collatz és incloure tots els nombres enters, no només els enters positius. Deixant de banda el cicle 0 → 0 que no es pot introduir des de l'exterior, hi ha un total de quatre cicles coneguts, en els quals tots els enters diferents de zero semblen caure eventualment sota la iteració de ''{{mvar|ƒ}}''. Aquests cicles s'enumeren aquí, començant pel conegut cicle per a ''n'' positiu:

Els valors senars es mostren en negreta gran. Cada cicle apareix en primer lloc amb el seu membre de [[valor absolut]] mínim (que sempre és senar).

{| class=wikitable style="text-align: center;"
! Cicle !! Durada del cicle de valor imparell !! Durada del cicle complet
|-
|style="text-align: left;"| <big>'''1'''</big> → 4 → 2 → <big>'''1'''</big> '''...''' || 1 || 3
|-
|style="text-align: left;"| <big>'''−1'''</big> → −2 → <big>'''−1'''</big> '''...''' || 1 || 2
|-
|style="text-align: left;"| <big>'''−5'''</big> → −14 → <big>'''−7'''</big> → −20 → −10 → <big>'''−5'''</big> '''...''' || 2 || 5
|-
|style="text-align: left;"| <big>'''−17'''</big> → −50 → <big>'''−25'''</big> → −74 → <big>'''−37'''</big> → −110 → <big>'''−55'''</big> → −164 → −82 → <big>'''−41'''</big> → −122 → <big>'''−61'''</big> → −182 → <big>'''−91'''</big> → −272 → −136 → −68 → −34 → <big>'''−17'''</big> '''...''' || 7 || 18
|}

La ''conjectura generalitzada de Collatz'' és l'afirmació que cada nombre enter, sota la iteració de ''{{mvar|ƒ}}'', finalment cau en un dels quatre cicles anteriors o el cicle 0 → 0. (El cicle 0 → 0 només s'inclou per a la completesa).

=== Iteració sobre racionals amb denominadors senars ===
El mapa de Collatz es pot estendre a [[Nombre racional|nombres racionals]] ([[Nombre positiu|positius]] o [[Nombre negatiu|negatius]]) que tenen [[Fracció|denominadors]] senars quan s'escriuen en termes més baixos.

El nombre es considera ''«parell»'' o ''«senar»'' segons si el seu [[Fracció|numerador]] és parell o senar. Aleshores, la fórmula del mapa és exactament la mateixa que quan el [[Domini (matemàtiques)|domini]] són els [[Nombre enter|nombres enters]]: un racional ''«parell»'' d'aquest tipus es divideix per 2; un racional ''«senar»'' es multiplica per 3 i després s'afegeix 1. Un fet estretament relacionat és que el mapa de Collatz s'estén a l'[[Anell (matemàtiques)|anell]] de [[Nombre p-àdic|nombres enters ''2''-àdics]], que conté l'anell de racionals amb denominadors senars com a subanell.

Quan s'utilitza la definició de ''«drecera»'' del mapa de Collatz, se sap que qualsevol seqüència de paritat periòdica és generada per exactament un racional.{{sfn|Lagarias|1990|p=33-53}} Per contra, es conjectura que tot racional amb un denominador senar té una seqüència de paritat eventualment cíclica (''Conjectura de periodicitat'').{{sfn|Lagarias|1985|p=3-23}}

Si un ''cicle de paritat'' té una longitud ''n'' i inclou nombres senars exactament ''m'' vegades als índexs {{math|''k''<sub>0</sub> < ⋯ < ''k''<sub>''m''−1</sub>}}, llavors l'únic racional que genera immediatament i periòdicament aquest cicle de paritat és
{{NumBlk|:|<math>\frac{3^{m-1} 2^{k_0} + \cdots + 3^0 2^{k_{m-1}}}{2^n - 3^m}.</math>|{{EquationRef|1}}}}

Per exemple, el cicle de paritat {{nowrap|(1 0 1 1 0 0 1)}} té una longitud de 7 i quatre termes senars als índexs 0, 2, 3 i 6. Això és generat repetidament per la fracció
::<math>\frac{3^3 2^0 + 3^2 2^2 + 3^1 2^3 + 3^0 2^6}{2^7 - 3^4} = \frac{151}{47}</math>
ja que aquest últim condueix al cicle racional 
::<math>\frac{151}{47} \rightarrow \frac{250}{47} \rightarrow \frac{125}{47} \rightarrow \frac{211}{47} \rightarrow \frac{340}{47} \rightarrow \frac{170}{47} \rightarrow \frac{85}{47} \rightarrow \frac{151}{47} .</math>

Qualsevol [[permutació]] cíclica de (1 0 1 1 0 0 1) s'associa a una de les fraccions anteriors. Per exemple, el cicle (0 1 1 0 0 1 1) és produït per la fracció
::<math>\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{250}{47} . </math>

Per a una correspondència un a un, un cicle de paritat hauria de ser irreductible, és a dir, no dividible en subcicles idèntics. Com a il·lustració d'això, el cicle de paritat (1 1 0 0 1 1 0 0) i el seu subcicle (1 1 0 0) estan associats a la mateixa fracció {{sfrac|5|7}} quan es redueix als termes més baixos.

En aquest context, assumir la validesa de la conjectura de Collatz implica que (1 0) i (0 1) són els únics cicles de paritat generats per nombres enters positius (1 i 2, respectivament).

Si el denominador senar ''d'' d'un racional no és [[múltiple]] de 3, aleshores tots els iterats tenen el mateix denominador i la seqüència de numeradors es pot obtenir aplicant la generalització «{{math|3''n'' + ''d''}}» de la funció de Collatz.{{sfn|Belaga|Mignotte|1998|p=145-151}}
::<math> T_d(x) = \begin{cases}
 \frac{x}{2} &\text{si } x \equiv 0 \pmod{2},\\[4px]
 \frac{3x+d}{2} & \text{si } x\equiv 1 \pmod{2}.
\end{cases}</math>

=== Extensió ''2''-àdica ===
La funció 
::<math> T(x) = \begin{cases} \frac{x}{2} &\text{si } x \equiv 0 \pmod{2}\\[4px] \frac{3x+1}{2} & \text{si } x\equiv 1 \pmod{2} \end{cases}</math>
està ben definit a l'anell <math>\mathbb{Z}_2</math> de [[Nombre p-àdic|nombres enters ''2''-àdics]], on és continu i [[Sistema dinàmic mesurat|conserva la mesura]] respecte a la mesura ''2''-àdica. A més, se sap que la seva dinàmica és [[Teoria ergòdica|ergòdica]].{{sfn|Lagarias|1985|p=3-23}}

Definim la ''funció vectorial de paritat'' {{mvar|Q}} sobre la qual actua <math>\mathbb{Z}_2</math> com
::<math> Q(x) = \sum_{k=0}^{\infty} \left(T^k (x) \mod 2 \right) 2^k .</math>

La funció ''Q'' és una [[isometria]] ''2''-àdica.{{sfn|Bernstein|Lagarias|1996|p=1154-1169}} En conseqüència, cada seqüència de paritat infinita es produeix exactament per a un enter ''2''-àdic, de manera que [[Gairebé tots|gairebé totes]] les trajectòries són acícliques en <math>\mathbb{Z}_2</math>.

Una formulació equivalent de la conjectura de Collatz és aquesta
::<math> Q\left(\mathbb{Z}^{+}\right) \subset \tfrac13 \mathbb{Z}.</math>

=== Iteració sobre nombres reals o complexos ===
El mapa de Collatz (amb drecera) es pot veure com la restricció als nombres enters del [[Mapa (matemàtiques)|mapa]] [[Funció suau|suau]]
::<math>f(z)=\frac{1}{2} z \cos^2\left(\frac{\pi}{2} z\right)+\frac{3z+1}{2} \sin^2\left(\frac{\pi}{2} z\right).</math>

Les iteracions d'aquest mapa a la [[Recta real|línia real]] condueixen a un [[sistema dinàmic]], investigat més endavant per Chamberland.{{sfn|Chamberland|1996|p=495-509}} Ell va demostrar que la conjectura no val per als [[Nombre real|nombres reals]] positius, ja que hi ha una infinitat de punts fixos, així com òrbites que escapen monòtonament a l'infinit. La funció {{mvar|ƒ}} té dos cicles d'atracció de període 2, (1; 2) i (1,1925...; 2,1386...). A més, es conjectura que el conjunt d'òrbites il·limitades és de [[Mesura de Lebesgue|mesura]] 0.

<gallery mode="packed" heights="300">
Fitxer:CobwebCollatz2.PNG|[[Diagrama de Verhulst]] de l'òrbita 10-5-8-4-2-1-2-1-2-1-etc. en l'extensió real del mapa de Collatz (optimitzat mitjançant la substitució "{{math|3''n'' + 1}}" amb "{{math|(3''n'' + 1)/2}}")
Fitxer:CollatzFractal.png|Mapa [[fractal]] de Collatz en un veïnat de la línia real
</gallery>

''[Letherman, Schleicher i Wood 1999]'' van ampliar l'estudi al [[pla complex]], on la majoria dels punts tenen òrbites que divergeixen fins a l'infinit ''(regió acolorida a la il·lustració superior)''.{{sfn|Letherman|Schleicher|Wood|1999|p=241-252}} El límit entre la regió de color i els [[Classificació dels components Fatou|components]] negres, és a dir, el [[conjunt de Julia]] de ''{{mvar|ƒ}}'', és un patró fractal, de vegades anomenat ''«fractal de Collatz»''.

== Optimitzacions ==
Si ''n'' és [[múltiple]] de 4, es pot dividir directament per 4.
: ''Motiu'': inicialment és parell. Dividit per dos, encara és parell, de manera que es pot dividir per dos per segona vegada.

De manera més general, en [[Factorització|factoritzar]] abans de ''n'' és possible substituir la [[potència de dos]] per 2<sup>0</sup> = 1.
: ''Motiu'': si la potència de 2 en la primera factorització és major que 0, aleshores el nombre és parell, i en el punt següent tindrem la mateixa factorització amb 2 elevat a una potència inferior a 1. En repetir l'operació, s'arriba a 2<sup>0</sup>.
: ''Per exemple'': en comptes de 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (17 passos), es pot calcular 15, 46 (2<sup>1</sup>×23), 23, 70 (2<sup>1</sup>×35), 35, 106 (2<sup>1</sup>×53), 53, 160 (2<sup>5</sup>×5), 5, 16 (2<sup>4</sup>), 1 (11 passos).

Si ''n'' és senar, es pot fer (3''n'' + 1) / 2, saltant un pas.
: ''Motiu'': si n és senar, 3''n'' també és senar (el producte de dos nombres senars sempre és senar) i 3''n'' + 1 és parell, de manera que es pot dividir per dos.
: ''Per exemple'': 3 × 35 + 1 = 106.

3''m'' + 1 sempre forma part de la seqüència de 4''m'' + 1. Així, si ''n'' ≡ 1 (mod 4), ''n'' es pot convertir a (''n'' - 1) / 4 tantes vegades com sigui possible, estalviant un pas cada vegada. El nombre obtingut, parell o senar, s'ha de convertir posteriorment en 3''n'' + 1.
: ''Motiu'': 4''m'' + 1 sempre és senar, de manera que es convertirà en 3 (4''m'' + 1) + 1 = 12''m'' + 4 = 4 (3''m'' + 1), i es pot dividir per quatre.
: ''Per exemple'': 405 es pot convertir com a: 405 → 101 → 25 → 6 → 19. La seqüència normal de Collatz també conté 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19.

L'anterior es pot utilitzar per a una nova formulació, equivalent a l'anterior, de la funció de Collatz:

:<math> f(n) = \begin{cases}
\frac{n}{4}, & \text{si } n \equiv 0, \\
3 g(n)+1, & \text{si } n \equiv 1, \\
\frac{n}{2}, & \text{si } n \equiv 2, \\
\frac{1}{2}(3n+1), & \text{si } n \equiv 3,
\end{cases} \pmod{4} </math>

:<math> g(n) = \begin{cases}
n, & \text{si } n \not\equiv 1, \\
g(\frac{n-1}{4}), & \text{si } n \equiv 1,
\end{cases} \pmod{4} </math>

=== Compartiment temps-espai ===
La secció ''Com a seqüència de paritat'' d'aquest article ofereix una manera d'accelerar la simulació de la seqüència. Per avançar ''k'' passos a cada iteració (utilitzant la funció ''{{mvar|ƒ}}'' d'aquesta secció), es divideix el nombre actual en dues parts, ''b'' (els ''k'' [[Bit|bits]] menys significatius, interpretats com un nombre enter) i ''a'' (la resta dels bits com a un nombre enter). El resultat de saltar endavant ''k'' passos es pot trobar com:

:{{math|''ƒ''<sup>''k''</sup> (2<sup>''k''</sup>''a'' + ''b'') {{=}} 3<sup>''c''(''b'')</sup>''a'' + ''d''(''b'')}}.

Les matrius ''c'' (o millor {{math|3<sup>''c''</sup>}}) i ''d'' es calculen prèviament per a tots els nombres ''b'' de ''k'' bits possibles, on ''d(b)'' és el resultat d'aplicar la funció ''{{mvar|ƒ}} k'' vegades a ''b'', i ''c(b'') és el nombre de nombres senars. trobada pel camí. Per exemple, si ''k'' = 5, es pot avançar 5 passos a cada iteració separant els 5 [[Bit menys significatiu|bits menys significatius]] d'un nombre i utilitzant:

: {{mvar|c}}(0...31) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 }
: {{mvar|d}}(0...31) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.

Això requereix una [[precomputació]] i un emmagatzematge de {{math|2<sup>''k''</sup>}} per accelerar el càlcul resultant per un factor de ''k'', un [[compromís espai-temps]].

=== Restriccions modulars ===
Amb el propòsit especial de cercar un [[contraexemple]] a la conjectura de Collatz, aquesta precomputació condueix a una acceleració encara més important, utilitzada per Tomás Oliveira e Silva en les seves confirmacions computacionals de la conjectura de Collatz fins a grans valors de ''n''. Si, per a alguns ''b'' i ''k'' donats, la [[Desigualtat matemàtica|desigualtat]]

:{{math|''ƒ''<sup>''k''</sup> (2<sup>''k''</sup>''a'' + ''b'') {{=}} 3<sup>''c''(''b'')</sup>''a'' + ''d''(''b'') < 2<sup>''k''</sup>''a'' + ''b''}}

s'aplica per a tot ''a'', aleshores el primer [[contraexemple]], si existeix, no pot ser ''b'' mod 2<sup>''k''</sup>.{{sfn|Garner|1981|p=19-22}} Per exemple, el primer contraexemple ha de ser senar perquè {{math|''f''(2''n'') {{=}} ''n''}}, menor que 2''n''; i ha de ser 3 mod 4 perquè {{math|''ƒ''<sup>2</sup> (4''n'' + 1) {{=}} 3''n'' + 1}}, menor que 4''n'' + 1. Per a cada valor inicial ''a'' que no sigui un contraexemple a la conjectura de Collatz, hi ha una ''k'' per a la qual es compleix aquesta [[Desigualtat matemàtica|desigualtat]], per tant, comprovar la conjectura de Collatz per a un valor inicial és tan bo com comprovar una classe de [[Congruència sobre els enters|congruència]] sencera. A mesura que ''k'' augmenta, la cerca només necessita comprovar aquells residus ''b'' que no s'eliminen per valors inferiors de ''k''. Només sobreviu una fracció exponencialment petita dels residus.<ref group="Nota">''[Lagarias 1985]'', Teorema D.</ref> Per exemple, els únics residus supervivents mod 32 són 7, 15, 27 i 31.

== Funció de Syracuse ==
Si ''k'' és un nombre enter senar, aleshores {{math|3''k'' + 1}} és parell, per tant {{math|3''k'' + 1 {{=}} 2<sup>''a''</sup>''k′''}} amb {{math|''k′''}} senar i {{math|''a'' ≥ 1}}a. La ''funció de Syracuse'' és la funció {{mvar|ƒ}} del conjunt {{mvar|I}} d'enters senars en si mateix, per a la qual {{math|''ƒ''(''k'') {{=}} ''k′''}} {{OEIS|id=A075677}}.

Algunes propietats de la funció de Syracuse són:
* Per a tot {{math|''k'' ∈ ''I''}}, {{math|''ƒ''(4''k'' + 1) {{=}} ''ƒ''(''k'')}}. (per que {{math|3(4''k'' + 1) + 1 {{=}} 12''k'' + 4 {{=}} 4(3''k'' + 1)}}.)
* De manera més general: Per a tots {{math|''p'' ≥ 1}} i senar {{mvar|h}}, {{math|''ƒ''<sup>''p''-1</sup> (2<sup>''p''</sup>''h'' − 1) {{=}} 2 × 3<sup>''p'' − 1</sup>''h'' − 1}}. (Aquí {{math|''ƒ''<sup>''p''-1</sup>}} és la [[Composició de funcions|notació d'iteració de funcions]]).
* For all odd {{mvar|h}}, {{math|''ƒ''(2''h'' − 1) ≤ {{sfrac|3''h'' − 1|2}}}}

La conjectura de Collatz és equivalent a l'enunciat que, «per a tot ''k'' en ''I'', existeix un nombre enter {{math|''n'' ≥ 1}} de tal manera que {{math|''ƒ''<sup>''n''</sup> (''k'') {{=}} 1}}».

== Generalitzacions indecidibles ==
El 1972, [[John Horton Conway]] va demostrar que una generalització natural del problema de Collatz és [[Algorisme|algorítmicament]] [[Problema indecidible|indecidible]].{{sfn|Conway|1972|p=49-52}}

Concretament, es consideren les funcions de la forma
::<math> {g(n) = a_i n + b_i} \;\;, \text{on} \;{n\equiv i \pmod P}</math>
i {{math|''a''<sub>0</sub>, ''b''<sub>0</sub>, ..., ''a''<sub>''P'' − 1</sub>, ''b''<sub>''P'' − 1</sub>}} són [[Nombre racional|nombres racionals]] que són triats de tal manera que {{math|''g''(''n'')}} sempre és un nombre enter.

La ''funció estàndard de Collatz'' ve donada per {{math|''P'' {{=}} 2}}, {{math|''a''<sub>0</sub> {{=}} {{sfrac|1|2}}}}, {{math|''b''<sub>0</sub> {{=}} 0}}, {{math|''a''<sub>1</sub> {{=}} 3}}, {{math|''b''<sub>1</sub> {{=}} 1}}. Conway va demostrar que el problema:

: Donats ''g'' i ''n'', la seqüència d'iteracions {{math|''g<sup>k</sup>''(''n'')}} arriba a 1?

és indecidible, en representar el [[Problema de la parada|problema de l'aturada]] d'aquesta manera.

Més proper al problema de Collatz és el següent problema ''quantificat universalment'':

: Donats ''g'' i ''n'', la seqüència d'iteracions {{math|''g<sup>k</sup>''(''n'')}} arriba a 1, per a tot {{math|''n'' > 0}}?

Modificar la condició d'aquesta manera pot fer que un problema sigui més difícil o més fàcil de resoldre (intuïtivament, és més difícil justificar una resposta positiva, però pot ser més fàcil justificar-ne una negativa). ''[Kurtz i Simon 2007]''{{sfn|Kurtz|Simon|2007|p=542-553}} van demostrar que el problema anterior és, de fet, indecidible i encara més alt en la [[jerarquia aritmètica]], concretament {{math|Π{{su|b=2|p=0}}}}-complet. Aquest resultat de [[duresa]] es manté fins i tot si es restringeix la classe de funcions ''g'' fixant el mòdul ''P'' a 6480.{{sfn|Ben-Amram|2015|p=19-56}}

== Algorismes per calcular seqüències de Collatz ==
Es pot calcular fàcilment una seqüència de Collatz específica, tal com mostra l'exemple de [[pseudocodi]] següent:

 '''function''' collatz(n)
 '''while''' n > 1
 '''if''' n senar
 '''set''' n to 3n + 1
 '''else'''
 '''set''' n to n / 2

O, utilitzant la [[recursivitat]]:

 '''function''' collatz(n)
 '''if''' n > 1
 '''if''' n senar
 collatz(3n + 1)
 '''else'''
 collatz(n / 2)

Aquests programes acaben quan la seqüència arriba a 1, per evitar imprimir un [[Bucle (programació)|bucle]] infinit de 4, 2, 1. Si la conjectura de Collatz és certa, els [[Programari|programes]] sempre acaben, sigui quin sigui el nombre enter positiu inicial.

== Implementacions informàtiques ==
En llenguatge [[Python]]:<syntaxhighlight lang="python">
def collatz(x):
 while x > 1:
 if x % 2 == 0:
 x /= 2
 else:
 x = 3*x+1
</syntaxhighlight>

En llenguatge [[Java (llenguatge de programació)|Java]]:
<syntaxhighlight lang="java">
static void collatz(int x) {
	System.out.println(x);
	if (x>1) {
		collatz((x%2==0) ? x/2 : (3*x+1));
	}
}</syntaxhighlight>

En llenguatge [[Llenguatge C|C]]:
<syntaxhighlight lang="c">
void collatz(int x)
{	
	printf("%d ", x);	
	if (1 == x)
		return;
	else if (x % 2 == 0)		
		collatz(x/2);
	else
		collatz(3*x+1);
}</syntaxhighlight>

En llenguatge [[PHP]]:
<syntaxhighlight lang="php">
function collatz($x){
	if($x == 1){
		return $x; 
	}else if($x % 2 == 0){
		$result = $x / 2;
		return collatz($result);
	}else{
		$result = ($x * 3) + 1;
		return collatz($result);
	}
}</syntaxhighlight>

En llenguatge [[Haskell]]:
<syntaxhighlight lang="haskell">
collatz :: (Integral a) => a -> [a]
collatz 1 = [1]
collatz n 
 | even n = n:collatz (n `div` 2) 
 | odd n = n:collatz (n*3 + 1) 
</syntaxhighlight>

En llenguatge [[Ruby]]:
<syntaxhighlight lang="ruby">
def collatz(n)
 puts n
 return if n == 1
 return collatz(n*3 + 1) if n.odd?
 return collatz(n/2)
end
</syntaxhighlight>

== Nota històrica sobre els diferents noms ==
A principis de la [[dècada del 1930]], [[Lothar Collatz]], estudiant de la [[Universitat d'Hamburg]], es va dedicar a la [[teoria de nombres]] i la [[teoria de grafs]]. Va començar amb un nombre enter positiu, li va aplicar un [[algorisme]] [[Iteració|iteratiu]], va dibuixar els [[Graf (matemàtiques)|grafs]] associats i es va fer preguntes que encara no s'havien contestat.

El matemàtic alemany [[Helmut Hasse]], amic de Collatz, va difondre el problema, també conegut com a ''algorisme de Hasse'' o ''problema 3x + 1''.

Com que Hasse va presentar el problema a la [[dècada del 1950]] durant una visita a la [[Universitat de Syracuse]] (prop de [[Nova York]]), va proposar anomenar-lo el ''problema de Syracuse''.

El matemàtic polonès [[Stanisław Ulam|Stanislaw Ulam]] va fer circular l'algorisme al [[Laboratori Nacional Los Alamos|Laboratori Nacional de Los Alamos]], on va treballar durant la [[Segona Guerra Mundial]]. És per això que el problema també es coneix com el ''problema Ulam''.

A la [[dècada del 1960]], el matemàtic japonès [[Shizuo Kakutani]] es va tornar a interessar pel problema, de manera que la conjectura també s'anomena ''problema de Kakutani''.

== En la cultura popular ==
Segons el [[matemàtic]] [[Greg Muller]], la importància d'aquesta conjectura rau en el fet que ''«els matemàtics sospiten que la resolució de la conjectura de Collatz obrirà nous horitzons i desenvoluparà noves i importants tècniques en [[teoria de nombres]]»''. [[Derek Jennings]] comenta que ''«la raó és que, com que és fàcil de presentar i entendre, té el potencial d'atreure els joves a les matemàtiques. Jo mateix vaig saber de la seva existència a l'institut i no vaig poder resistir el seu encant»''.

A la pel·lícula canadenca ''[[Incendies]]'' (2010), un estudiant graduat en [[Matemàtica pura|matemàtiques pures]] explica la conjectura de Collatz a un grup d'estudiants de grau. Posa els seus estudis en suspens durant un temps per abordar algunes preguntes no resoltes sobre el passat de la seva família. Al final de la pel·lícula, la conjectura de Collatz resulta haver presagiat un descobriment inquietant i difícil que fa sobre la seva família.{{sfn|Emmer|2012|p=260-264}}<ref name="mazmanian">{{ref-publicació|cognom=Mazmanian|nom=Adam|títol=MOVIE REVIEW: 'Incendies'|url=https://www.washingtontimes.com/news/2011/may/19/movie-review-incendies/ |publicació=[[The Washington Times]]|data=19 de maig de 2011 |llengua=anglès}}</ref>

''The Ultimate Challenge: The {{nobr| 3{{mvar|x}} + 1 }} Problem'',{{sfn|Lagarias|2011}} publicat l'any 2010 per l'[[Societat Americana de Matemàtiques|American Mathematical Society]] i editat per [[Jeffrey Lagarias]], és un [[compendi]] d'informació sobre la conjectura de Collatz, mètodes per abordar-la i generalitzacions. Inclou dos articles d'investigació de l'editor i cinc d'altres autors sobre la història del problema, generalitzacions, enfocaments estadístics i resultats de la [[teoria de la computació]]. També inclou reimpressions dels primers articles sobre el tema, inclòs el document de [[Lothar Collatz]].

== Notes ==
<references group="Nota"/>

== Referències ==
{{referències}}

== Bibliografia ==
{{Div col|cols=2}}
* {{ref-publicació |cognom=Andrei |nom= Stefan |cognom2=Masalagiu |nom2= Cristian |doi=10.1007/s002360050117 |article=About the Collatz conjecture |any=1998 |publicació=Acta Informatica |volum=35 |llengua=anglès |p=167-179}}
* {{ref-publicació |cognom = Barina |nom = David |article = Convergence verification of the Collatz problem |publicació = The Journal of Supercomputing |any = 2020 |volum = 77(3) | doi = 10.1007/s11227-020-03368-x | s2cid = 220294340 |llengua=anglès}}
* {{ref-llibre| enllaçautor= Edward Belaga | cognom= Belaga | nom= Edward G. | citeseerx = 10.1.1.54.483 |títol = Reflecting on the 3x+1 Mystery |editorial = Universitat d'Estrasburg |any = 1998 |llengua=anglès}}
* {{ref-publicació |nom=Edward G. |cognom=Belaga |cognom2=Mignotte |nom2=Maurice |article=Embedding the 3x+1 Conjecture in a 3x+d Context |publicació=Experimental Mathematics |volum=7(2) |any=1998 |doi=10.1080/10586458.1998.10504364 |s2cid=17925995 |url=http://www.emis.de/journals/EM/expmath/volumes/7/7.html |llengua=anglès}}
* {{ref-llibre |nom=Edward G. |cognom=Belaga |cognom2=Mignotte |nom2=Maurice |capítol=Walking Cautiously into the Collatz Wilderness: Algorithmically, Number Theoretically, Randomly |títol=Fourth Colloquium on Mathematics and Computer Science : Algorithms, Trees, Combinatorics and Probabilities |data=18-22 de setembre de 2006 |editorial= Institut Élie Cartan |lloc=Nancy (França) |llengua=anglès}}
* {{ref-publicació |cognom=Ben-Amram |nom=Amir M. |any=2015 |article=Mortality of iterated piecewise affine functions over the integers: Decidability and complexity |publicació=Computability |doi=10.3233/COM-150032 |volum=1(1) |llengua=anglès}}
* {{ref-publicació|cognom=Bernstein|nom=Daniel J.|cognom2=Lagarias|nom2=Jeffrey C.|any=1996|article=The 3''x'' + 1 conjugacy map|publicació=[[Canadian Journal of Mathematics]]|volum=48(6)|doi=10.4153/CJM-1996-060-x|issn=0008-414X |llengua=anglès}}
* {{ref-llibre|cognom=Bruschi |nom= Mario |eprint=0810.5169 |títol=A generalization of the Collatz problem and conjecture |llengua=anglès|any=2008}}
* {{ref-publicació |nom=Marc |cognom=Chamberland |article=A continuous extension of the 3''x'' + 1 problem to the real line |publicació=Dynam. Contin. Discrete Impuls Systems |volum=2(4) |any=1996 |llengua=anglès}}
* {{ref-publicació |cognom=Conway |nom=John H. |any=1972 |article=Unpredictable iterations |publicació=Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder |llengua=anglès}} ''(conferència)''.
* {{ref-publicació |cognom = De Mol |nom = Liesbeth |article = Tag systems and Collatz-like functions |publicació = Theoretical Computer Science |volum = 390(1) |pàgina=92-101|mes=gener |any=2008 | url = http://logica.ugent.be/liesbeth/TagColOK.pdf |format={{PDF}} |llengua=anglès | doi=10.1016/j.tcs.2007.10.020}}
* {{ref-publicació|cognom=Eliahou|nom=Shalom|any=1993|títol=The 3''x'' + 1 problem: new lower bounds on nontrivial cycle lengths|publicació=Discrete Mathematics|volum=118(1)|doi=10.1016/0012-365X(93)90052-U|llengua=anglès}}
* {{ref-llibre|títol=Imagine Math: Between Culture and Mathematics|cognom=Emmer|nom=Michele|editorial=Springer Publishing |any=2012|isbn=978-8-847-02426-7 |llengua=anglès}}
* {{ref-llibre |cognom=Everest |nom=Graham |cognom2=van der Poorten |nom2=Alf | enllaçautor2=Alfred van der Poorten |cognom3=Shparlinski |nom3=Igor |cognom4=Ward |nom4=Thomas |títol=Recurrence sequences |col·lecció=Mathematical Surveys and Monographs |volum=104 |lloc=Providence, Rhode Island |editorial=[[American Mathematical Society]] |any=2003 | isbn=0-8218-3387-1 | zbl=1033.11006 | capítol=3.4 |llengua=anglès}}
* {{ref-publicació |cognom=Garner |nom=Lynn E. |any=1981 |article=On the Collatz 3''n'' + 1 algorithm |publicació=[[Proceedings of the American Mathematical Society]] | volum=82(1) |doi=10.1090/S0002-9939-1981-0603593-2 |llengua=anglès |jstor=2044308}}
* {{ref-llibre|cognom=Gasull i Embid | nom = Armengol | títol = Fes Matemàtiques! | any = 2001 | editorial = [[Universitat Autònoma de Barcelona]] | llengua = català | pàgina= 93 i seg. |isbn=84-490-2260-6}}
* {{ref-publicació |cognom=Guy |nom=R. K. |any=1983 |article=Don't try to solve these problems |publicació=Amer. Math. Monthly |volum=90(1) |jstor=2975688 |doi=10.2307/2975688 |llengua=anglès}} By this Erdos means that there aren't powerful tools for manipulating such objects.
* {{ref-llibre |cognom=Guy |nom=Richard K. |enllaçautor=Richard K. Guy |títol=Unsolved Problems in Number Theory |editorial=Springer-Verlag |any=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | capítol=E16: The 3x+1 problem |llengua=anglès}}
* {{ref-llibre |cognom=Hofstadter |nom=Douglas R. |enllaçautor=Douglas Hofstadter |any=1979 |títol=Gödel, Escher, Bach |editorial=Basic Books |lloc=Nova York |isbn=0-465-02685-0 |llengua=anglès}}
* {{ref-publicació |cognom = Krasikov |nom = Ilia |cognom2 = Lagarias |nom2 = Jeffrey C. |enllaçautor2 = Jeffrey Lagarias|any = 2003|article = Bounds for the 3''x'' + 1 problem using difference inequalities|publicació = Acta Arithmetica | url = https://www.impan.pl/download/pdf/aa109-3-4 | doi = 10.4064/aa109-3-4 | mr = 1980260 |volum = 109(3) | arxiv = math/0205002 | bibcode = 2003AcAri.109..237K | s2cid = 18467460 |llengua=anglès}}
* {{ref-llibre |cognom=Kurtz |nom=Stuart A. |cognom2=Simon |nom2=Janos |any=2007 |capítol=The undecidability of the generalized Collatz problem |títol=Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007 |isbn=978-3-540-72503-9 |doi=10.1007/978-3-540-72504-6_49 |llengua=anglès}} Com a [http://www.cs.uchicago.edu/~simon/RES/collatz.pdf Collatz] {{PDF}}.
* {{ref-publicació | cognom = Lagarias | nom = Jeffrey C. |enllaçautor=Jeffrey C. Lagarias |article = The 3''x'' + 1 problem and its generalizations | jstor=2322189 | llengua =anglès| publicació = The American Mathematical Monthly | volum = 92(1) | any = 1985 |doi=10.1080/00029890.1985.11971528}}
* {{ref-publicació|cognom=Lagarias|nom=Jeffrey|any=1990|article=The set of rational cycles for the 3x+1 problem|url=https://eudml.org/doc/206298 |publicació=Acta Arithmetica |volum=56(1)|issn=0065-1036|doi=10.4064/aa-56-1-33-53|llengua=anglès}}
* {{ref-llibre |nom=Jeffrey C.|cognom= Lagarias|eprint=math.NT/0608208 |títol=The 3''x'' + 1 problem: An annotated bibliography, II (2000-) |llengua=anglès |any=2006}}
* {{ref-llibre|cognom=Lagarias | nom = Jeffrey C. | títol = The Ultimate Challenge: The 3''x'' + 1 Problem | any = 2011 | editorial = [[American Mathematical Society]] | lloc = Providence | llengua = anglès| isbn = 978-08218-4940-8}}
* {{ref-publicació |cognom=Leavens |nom=Gary T. |cognom2=Vermeulen |nom2=Mike |mes=desembre |any=1992 |article=3''x'' + 1 search programs |publicació=Computers & Mathematics with Applications |volum=24(11) |doi=10.1016/0898-1221(92)90034-F|llengua=anglès}}
* {{ref-publicació |nom=Simon |cognom=Letherman |nom2=Dierk |cognom2=Schleicher |nom3=Reg |cognom3=Wood |article=The (3''n'' + 1)-problem and holomorphic dynamics |publicació=Experimental Mathematics |volum=8(3) |any=1999 |doi= 10.1080/10586458.1999.10504402 |llengua=anglès}}
* {{ref-llibre |cognom=Maddux |nom=Cleborne D. |cognom2=Johnson |nom2=D. Lamont |any=1997 |títol=Logo: A Retrospective |editorial=Haworth Press |lloc=Nova York |isbn=0-7890-0374-0 | llengua=anglès}} The problem is also known by several other names, including: Ulam's conjecture, the Hailstone problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and the Collatz problem.
* {{ref-llibre|cognom= O'Connor|nom=J. J.|cognom2=Robertson|nom2=E. F.|títol=Lothar Collatz|any=2006|url=http://www-history.mcs.st-andrews.ac.uk/Biographies/Collatz.html |editorial=St Andrews University School of Mathematics and Statistics |lloc=Escòcia |llengua=anglès}}
* {{ref-llibre |cognom = Ohira |nom = Reiko |cognom2 = Yamashita |nom2 = Michinori |url = http://risweb2.ris.ac.jp/faculty/earth_env/yamasita/open/p-col.pdf |format = {{PDF}} |llengua = japonès |títol = Una generalització del problema de Collatz }} {{Webarchive|url=https://web.archive.org/web/20120330191814/http://risweb2.ris.ac.jp/faculty/earth_env/yamasita/open/p-col.pdf |date=2012-03-30 }}
* {{ref-llibre |cognom=Pickover |nom=Clifford A. |any=2001 |títol=Wonders of Numbers |editorial=[[Oxford University Press]] |lloc=Oxford |isbn=0-19-513342-0 |llengua=anglès}}
* {{ref-publicació |cognom=Simons |nom=John L. |any=2005 |article=On the nonexistence of 2-cycles for the 3''x'' + 1 problem |publicació=Math. Comp. |volum=74 |mr=2137019 |doi=10.1090/s0025-5718-04-01728-4|bibcode=2005MaCom..74.1565S |llengua=anglès}}
* {{ref-publicació |nom=J. |cognom=Simons |nom2=B. |cognom2=de Weger |article=Theoretical and computational bounds for ''m''-cycles of the 3''n'' + 1 problem |publicació=Acta Arithmetica |volum=117(1) |any=2005 |doi=10.4064/aa117-1-3 |url=http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n+1-ActaArith%5B2005%5D.pdf |format={{PDF}} |bibcode=2005AcAri.117...51S |llengua=anglès |consulta=2022-11-16 |arxiuurl=https://web.archive.org/web/20170517124216/http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n%201-ActaArith%5B2005%5D.pdf |arxiudata=2017-05-17 }}
* {{ref-web |nom = Matti K. |cognom = Sinisalo |url = http://geocities.com/mattiksinisalo/collatz.doc |títol = On the minimal cycle lengths of the Collatz sequences |mes = juny |any = 2003 |obra = Universitat d'Oulu |llengua = anglès |consulta = 2022-11-16 |arxiuurl = https://web.archive.org/web/20091024183537/http://geocities.com/mattiksinisalo/collatz.doc |arxiudata = 2009-10-24 }}
* {{ref-publicació |cognom=Sinyor |nom= J. |url=http://downloads.hindawi.com/journals/ijmms/2010/458563.pdf |format={{PDF}} |article=The 3x+1 Problem as a String Rewriting System |publicació=International Journal of Mathematics and Mathematical Sciences |volum=2010 |any=2010 |pàgina=Article ID 458563, 6 pàgines |llengua=anglès}}
* {{ref-web |nom = Paul |cognom = Stadfeld |url = http://home.versatel.nl/galien8/blueprint/blueprint.html |títol = Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture |llengua = anglès |consulta = 2022-11-16 |arxiuurl = https://web.archive.org/web/20070926231400/http://home.versatel.nl/galien8/blueprint/blueprint.html |arxiudata = 2007-09-26 }}
* {{ref-llibre |nom=R. P. |cognom=Steiner |capítol=A theorem on the syracuse problem |títol=Proceedings of the 7th Manitoba Conference on Numerical Mathematics |any=1977 |pàgina=553–559 |mr=535032 |llengua=anglès}}
* {{ref-publicació |cognom = Terras |nom = Riho |any = 1976 |article = A stopping time problem on the positive integers |publicació = Acta Arithmetica | mr = 0568274 |volum = 30(3) |pàgina = 241–252 | url = http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf |format={{PDF}} |doi=10.4064/aa-30-3-241-252| llengua=anglès}}
* {{ref-web |cognom = Urata |nom = Toshio |format = {{PDF}} |url = http://auemath.aichi-edu.ac.jp/~turata/Fall.files/CTZVI.pdf |títol = Some Holomorphic Functions connected with the Collatz Problem |llengua = anglès |consulta = 2022-11-16 |arxiuurl = https://web.archive.org/web/20041128171946/http://auemath.aichi-edu.ac.jp/~turata/Fall.files/CTZVI.pdf |arxiudata = 2004-11-28 }}
* {{ref-publicació |nom=Jean Paul |cognom=Van Bendegem |article=The Collatz Conjecture: A Case Study in Mathematical Problem Solving |publicació=Logic and Logical Philosophy |volum=14 |any=2005 |doi=10.12775/llp.2005.002 |url=https://compmath.files.wordpress.com/2008/08/jpvb_collatz.pdf |format={{PDF}} |llengua=anglès |p=7-23 |consulta=2022-11-16 |arxiuurl=https://ghostarchive.org/archive/20221009/https://compmath.files.wordpress.com/2008/08/jpvb_collatz.pdf |arxiudata=2022-10-09 }}
{{Div col end}}

== Vegeu també ==
* [[Aritmètica modular]]
* [[Dinàmica aritmètica]]
* [[Grup afí a classe de residus]]
* [[Semigrup 3x + 1|Semigrup {{math|3''x'' + 1}}]]

== Enllaços externs ==
* {{ref-web |url=http://www.numbertheory.org/3x+1/ |nom=Keith |cognom=Matthews |títol={{nobr|3 {{mvar|x}} + 1}} page |llengua=anglès}}
* {{MathWorld | urlname=CollatzProblem |títol=Collatz Problem}}
* {{PlanetMath | urlname=CollatzProblem |títol=Collatz Problem}}.
* {{ref-web |nom=Jesse |cognom=Nochella |títol=Collatz Paths |obra=[[Wolfram Demonstrations Project]] |url=http://demonstrations.wolfram.com/CollatzPaths/ |llengua=anglès}}
* {{ref-web |url=https://www.technologyreview.com/2021/07/02/1027475/computers-ready-solve-this-notorious-math-problem/ |títol=Are computers ready to solve this notoriously unwieldy math problem? |obra=Technology Review |llengua=anglès}}

{{Autoritat}}

[[Categoria:Conjectures]]
[[Categoria:Problemes matemàtics]]