Conjectura de Collatz

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.

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.

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.[1] 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), l'algoritme de Hasse (per Helmut Hasse), o el problema de Syracuse (per la Universitat americana de Syracuse que hi va dedicar molts esforços).[Nota 1][2]

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),[Nota 2][3][4] o com a nombres meravellosos.[5]

Paul Erdős va dir sobre la conjectura de Collatz: «Les matemàtiques potser no estan preparades per a aquests problemes».[6] També va oferir 500 US$ per la seva solució.[7] 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».[8]

Enunciat del problema modifica

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 dóna 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 modifica

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 (successió A008884 a l'OEIS)

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, ... (successió A006877 a l'OEIS).

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, ... (successió A006884 a l'OEIS)

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, ... (successió A006577 a l'OEIS)

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 77.031, que té 350 passos,
menor que 106 és 837.799, que té 524 passos,
menor que 107 és 8.400.511, que té 685 passos,
menor que 108 és 63.728.127, que té 949 passos,
menor que 10⁹ és 670.617.279, que té 986 passos,
menor que 1010 és 9.780.657.630, que té 1132 passos,[9]
menor que 1011 és 75.128.138.247, que té 1228 passos,
menor que 1012 és 989.345.275.647, que té 1348 passos.[10]

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 modifica

Arguments de suport modifica

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 modifica

A partir del 2020, la conjectura s'ha verificat per ordinador per a tots els valors inicials fins a 2682,95×1020. Tots els valors inicials provats fins ara acaben en el cicle de repetició (4; 2; 1) del període 3.[11]

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.[12][13][14]

Una heurística probabilística modifica

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 3/4 de l'anterior (més precisament, la mitjana geomètrica de les proporcions dels resultats és 3/4).[Nota 3] 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 modifica

Com ha demostrat Riho Terras, gairebé tots els nombres enters positius tenen un temps d'aturada finit.[15] 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».[16][17]

Límits inferiors modifica

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 x0.84 per a tots els x prou grans.[18]

Cicles modifica

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

 

Un cicle és una seqüència (a0, a1, ..., aq) de diferents nombres enters positius on ƒ(a0) = a1, ƒ(a1) = a, ..., i ƒ(aq) = a0.

L'únic cicle conegut és (1,2) del període 2, anomenat cicle trivial.

Llargada del cicle modifica

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 a, b i c són nombres enters no negatius, b ≥ 1 i ac = 0. Aquest resultat es basa en l'expansió de la fracció contínua ln 3/ln 2.[13]

k-cicles modifica

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.[14] 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).[19] [Simons 2005] va utilitzar el mètode de Steiner per demostrar que no hi ha 2-cicles.[20] [Simons i de Weger 2005] van ampliar aquesta demostració fins a 68-cicles; no hi ha k-cicles fins a k = 68.[14] Per a cada k més enllà de 68, aquest mètode dóna 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.[14] 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.[11] 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 modifica

A l'invers modifica

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

 

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, n − 1/3 ≡ 1 (mod 2) si i només si n ≡ 4 (mod 6). Conjecturalment, aquesta relació inversa forma un arbre excepte per al 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 3n + 1/2, el graf de Collatz es defineix per la relació inversa,

 

Per a qualsevol nombre enter n, n ≡ 1 (mod 2) si i només si 3n + 1/2 ≡ 2 (mod 3). De manera equivalent, 2n − 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ó ƒ(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 2 més alta que divideix n′ (sense 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, ƒk(n) = 1). Aleshores, en binari, el nombre n es pot escriure com la concatenació de cadenes wk wk−1 ... w1 on cada wh és un extracte finit i contigu de la representació de 1/3h.[21] Per tant, la representació de n té les repeticions de 1/3h, on cada repetició es gira opcionalment i després es replica fins a un nombre finit de bits. És només en binari que això passa.[22] 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 modifica

Les aplicacions repetides de la funció Collatz es poden representar com una màquina abstracta que gestiona cadenes de 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 modifica

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

         111
        1111
       10110
      10111
     100010
    100011
    110100
   11011
  101000
 1011
10000

Com a seqüència de paritat modifica

Per a aquesta secció, considerem la funció de Collatz en la forma lleugerament modificada

 

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, P(2n) = 0 i P(2n + 1) = 1, llavors podem definir la seqüència de paritat de Collatz (o vector de paritat) per a un nombre n com pi = P(ai), on a0 = n, i ai+1 = ƒ(ai).

Quina operació es realitza, 3n + 1/2 o 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 ƒ(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 2k. 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.[15][23]

L'aplicació de la funció ƒ k vegades al nombre n = 2ka + b donarà el resultat 3ca + 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 25a + 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 33a + 2; per a 22a + 1 només hi ha 1 augment quan 1 puja a 2 i baixa a 1, de manera que el resultat és 3a + 1. Quan b és 2k − 1, hi haurà k augments i el resultat serà 2 × 3ka − 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, 4a + 1 es converteix en 3a + 1 després de dues aplicacions de ƒ i 16a + 3 es converteix en 9a + 2 després de 4 aplicacions de ƒ. Però que aquests nombres més petits continuïn fins a 1 depèn del valor de a.

Com a sistema d'etiquetes modifica

Per a la funció de Collatz en la forma

 

Les seqüències de calamarsa es poden calcular mitjançant el sistema extremadament senzill de 2-etiquetes amb regles de producció

abc, ba, caaa.

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]).

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)

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 modifica

Iteració sobre tots els nombres enters modifica

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 ƒ. 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).

Cicle Durada del cicle de valor imparell Durada del cicle complet
1 → 4 → 2 → 1 ... 1 3
−1 → −2 → −1 ... 1 2
−5 → −14 → −7 → −20 → −10 → −5 ... 2 5
−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17 ... 7 18

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

Iteració sobre racionals amb denominadors senars modifica

El mapa de Collatz es pot estendre a nombres racionals (positius o negatius) que tenen denominadors senars quan s'escriuen en termes més baixos.

El nombre es considera «parell» o «senar» segons si el seu numerador és parell o senar. Aleshores, la fórmula del mapa és exactament la mateixa que quan el domini són els 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 de 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.[24] Per contra, es conjectura que tot racional amb un denominador senar té una seqüència de paritat eventualment cíclica (Conjectura de periodicitat).[23]

Si un cicle de paritat té una longitud n i inclou nombres senars exactament m vegades als índexs k0 < ⋯ < km−1, llavors l'únic racional que genera immediatament i periòdicament aquest cicle de paritat és

 

 

 

 

 

(1)

Per exemple, el cicle de paritat (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ó

 

ja que aquest últim condueix al cicle racional

 

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ó

 

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ó 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ó «3n + d» de la funció de Collatz.[25]

 

Extensió 2-àdica modifica

La funció

 

està ben definit a l'anell   de nombres enters 2-àdics, on és continu i conserva la mesura respecte a la mesura 2-àdica. A més, se sap que la seva dinàmica és ergòdica.[23]

Definim la funció vectorial de paritat Q sobre la qual actua   com

 

La funció Q és una isometria 2-àdica.[26] En conseqüència, cada seqüència de paritat infinita es produeix exactament per a un enter 2-àdic, de manera que gairebé totes les trajectòries són acícliques en  .

Una formulació equivalent de la conjectura de Collatz és aquesta

 

Iteració sobre nombres reals o complexos modifica

El mapa de Collatz (amb drecera) es pot veure com la restricció als nombres enters del mapa suau

 

Les iteracions d'aquest mapa a la línia real condueixen a un sistema dinàmic, investigat més endavant per Chamberland.[27] Ell va demostrar que la conjectura no val per als nombres reals positius, ja que hi ha una infinitat de punts fixos, així com òrbites que escapen monòtonament a l'infinit. La funció ƒ 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 0.

[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).[28] El límit entre la regió de color i els components negres, és a dir, el conjunt de Julia de ƒ, és un patró fractal, de vegades anomenat «fractal de Collatz».

Optimitzacions modifica

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 factoritzar abans de n és possible substituir la potència de dos per 20 = 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 20.
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 (21×23), 23, 70 (21×35), 35, 106 (21×53), 53, 160 (25×5), 5, 16 (24), 1 (11 passos).

Si n és senar, es pot fer (3n + 1) / 2, saltant un pas.

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

3m + 1 sempre forma part de la seqüència de 4m + 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 3n + 1.

Motiu: 4m + 1 sempre és senar, de manera que es convertirà en 3 (4m + 1) + 1 = 12m + 4 = 4 (3m + 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:

 
 

Compartiment temps-espai modifica

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ó ƒ d'aquesta secció), es divideix el nombre actual en dues parts, b (els k 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:

ƒk (2ka + b) = 3c(b)a + d(b).

Les matrius c (o millor 3c) 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ó ƒ 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 bits menys significatius d'un nombre i utilitzant:

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 }
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 2k per accelerar el càlcul resultant per un factor de k, un compromís espai-temps.

Restriccions modulars modifica

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

ƒk (2ka + b) = 3c(b)a + d(b) < 2ka + b

s'aplica per a tot a, aleshores el primer contraexemple, si existeix, no pot ser b mod 2k.[12] Per exemple, el primer contraexemple ha de ser senar perquè f(2n) = n, menor que 2n; i ha de ser 3 mod 4 perquè ƒ2 (4n + 1) = 3n + 1, menor que 4n + 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, per tant, comprovar la conjectura de Collatz per a un valor inicial és tan bo com comprovar una classe de 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.[Nota 4] Per exemple, els únics residus supervivents mod 32 són 7, 15, 27 i 31.

Funció de Syracuse modifica

Si k és un nombre enter senar, aleshores 3k + 1 és parell, per tant 3k + 1 = 2ak′ amb k′ senar i a ≥ 1a. La funció de Syracuse és la funció ƒ del conjunt I d'enters senars en si mateix, per a la qual ƒ(k) = k′ (successió A075677 a l'OEIS).

Algunes propietats de la funció de Syracuse són:

  • Per a tot kI, ƒ(4k + 1) = ƒ(k). (per que 3(4k + 1) + 1 = 12k + 4 = 4(3k + 1).)
  • De manera més general: Per a tots p ≥ 1 i senar h, ƒp-1 (2ph − 1) = 2 × 3p − 1h − 1. (Aquí ƒp-1 és la notació d'iteració de funcions).
  • For all odd h, ƒ(2h − 1) ≤ 3h − 1/2

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

Generalitzacions indecidibles modifica

El 1972, John Horton Conway va demostrar que una generalització natural del problema de Collatz és algorítmicament indecidible.[29]

Concretament, es consideren les funcions de la forma

 

i a0, b0, ..., aP − 1, bP − 1 són nombres racionals que són triats de tal manera que g(n) sempre és un nombre enter.

La funció estàndard de Collatz ve donada per P = 2, a0 = 1/2, b0 = 0, a1 = 3, b1 = 1. Conway va demostrar que el problema:

Donats g i n, la seqüència d'iteracions gk(n) arriba a 1?

és indecidible, en representar el 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 gk(n) arriba a 1, per a tot 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][30] van demostrar que el problema anterior és, de fet, indecidible i encara més alt en la jerarquia aritmètica, concretament Π0
2
-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.[31]

Algorismes per calcular seqüències de Collatz modifica

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 infinit de 4, 2, 1. Si la conjectura de Collatz és certa, els programes sempre acaben, sigui quin sigui el nombre enter positiu inicial.

Implementacions informàtiques modifica

En llenguatge Python:

def collatz(x):
    while x > 1:
       if x % 2 == 0:
            x /= 2
        else:
            x = 3*x+1

En llenguatge Java:

static void collatz(int x) {
	System.out.println(x);
	if (x>1) {
		collatz((x%2==0) ? x/2 : (3*x+1));
	}
}

En llenguatge 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);
}

En llenguatge 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);
	}
}

En llenguatge 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)

En llenguatge Ruby:

def collatz(n)
  puts n
  return if n == 1
  return collatz(n*3 + 1) if n.odd?
  return collatz(n/2)
end

Nota històrica sobre els diferents noms modifica

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 iteratiu, va dibuixar els 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 Stanislaw Ulam va fer circular l'algorisme al 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 modifica

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à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.[32][33]

The Ultimate Challenge: The 3x + 1 Problem,[8] publicat l'any 2010 per l'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 modifica

  1. 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.
  2. 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.
  3. [Lagarias 1985], secció "A heuristic argument".
  4. [Lagarias 1985], Teorema D.

Referències modifica

  1. O'Connor, 2006.
  2. Maddux i Johnson, 1997, p. 160.
  3. Pickover, 2001, p. 116-118.
  4. «Hailstone Number» (en anglès). MathWorld. Wolfram Research.
  5. Hofstadter, 1979, p. 400-402.
  6. Guy, 2004, p. 330-336.
  7. Guy, 1983, p. 35-41.
  8. 8,0 8,1 Lagarias, 2011.
  9. Leavens i Vermeulen, 1992, p. 79-99.
  10. Roosendaal, Eric. «3x+1 delay records». (Note: "Delay records" are total stopping time records)
  11. 11,0 11,1 Barina i 2020, 2681-2688.
  12. 12,0 12,1 Garner, 1981, p. 19-22.
  13. 13,0 13,1 Eliahou, 1993, p. 45-56.
  14. 14,0 14,1 14,2 14,3 Simons i de Weger, 2005, p. 51-70.
  15. 15,0 15,1 Terras, 1976, p. 241-252.
  16. Tao, Terence. «Almost all Collatz orbits attain almost bounded values» (en anglès). What's new, 10-09-2019.
  17. Hartnett, Kevin «Mathematician Proves Huge Result on 'Dangerous' Problem» (en anglès). Quanta Magazine.
  18. Krasikov i Lagarias, 2003, p. 237-258.
  19. Steiner, 1977, p. 553-559.
  20. Simons, 2005, p. 1565-1572.
  21. Colussi, Livio «The convergence classes of Collatz function» (en anglès). Theoretical Computer Science, 412(39), 09-09-2011, pàg. 5409-5419. DOI: 10.1016/j.tcs.2011.05.056.
  22. Hew, Patrick Chisan «Working in binary protects the repetends of 1/3h: Comment on Colussi's 'The convergence classes of Collatz function'» (en anglès). Theoretical Computer Science, 618, 07-03-2016, pàg. 135-141. DOI: 10.1016/j.tcs.2015.12.033.
  23. 23,0 23,1 23,2 Lagarias, 1985, p. 3-23.
  24. Lagarias, 1990, p. 33-53.
  25. Belaga i Mignotte, 1998, p. 145-151.
  26. Bernstein i Lagarias, 1996, p. 1154-1169.
  27. Chamberland, 1996, p. 495-509.
  28. Letherman, Schleicher i Wood, 1999, p. 241-252.
  29. Conway, 1972, p. 49-52.
  30. Kurtz i Simon, 2007, p. 542-553.
  31. Ben-Amram, 2015, p. 19-56.
  32. Emmer, 2012, p. 260-264.
  33. Mazmanian, Adam «MOVIE REVIEW: 'Incendies'» (en anglès). The Washington Times, 19-05-2011.

Bibliografia modifica

Vegeu també modifica

Enllaços externs modifica