Conjectură Collatz

Histogramă pentru numere de la 1 la 100 de milioane

Conjectura Collatz (cunoscută și sub numele de conjectura 3 n + 1 , conjectura Syracuse , conjectura Ulam , secvența Hailstone sau numerele Hailstone ) este o conjectură matematică încă nerezolvată. A fost enunțată pentru prima dată în 1937 de Lothar Collatz , de la care își ia numele.

Paul Erdős a spus despre această presupunere că „matematica nu este încă coaptă pentru probleme de acest tip” și a oferit 500 de dolari pentru soluția sa ^[1] .

Afirmarea problemei

Conjectura se referă la următorul algoritm:

Luați un număr întreg pozitiv n .
Dacă n = 1, algoritmul se termină.
Dacă n este par, împarte la două; în caz contrar, înmulțiți cu 3 și adăugați 1.

Sau, algebric:

f(n)={\begin{cases}{\frac {n}{2}},&{\text{se }}n{\text{ pari,}}\\3n+1,&{\text{se }}n{\text{ dispari.}}\end{cases}}

{\ displaystyle f (n) = {\ begin {cases} {\ frac {n} {2}} și {\ text {se}} n {\ text {even,}} \\ 3n + 1 și & { \ text {se}} n {\ text {odd.}} \ end {cases}}}

{\ displaystyle f (n) = {\ begin {cases} {\ frac {n} {2}} și {\ text {se}} n {\ text {chiar,}} \\ 3n + 1 și & { \ text {se}} n {\ text {odd.}} \ end {cases}}}

Este posibil să se formeze o secvență prin aplicarea funcției luând în mod repetat ca prim element orice număr întreg pozitiv și, la fiecare pas, se aplică funcția rezultatului anterior, adică:

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

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

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

De exemplu, începând cu n = 6, obținem secvența 6, 3, 10, 5, 16, 8, 4, 2, 1.

Conjectura Collatz afirmă că acest algoritm ajunge întotdeauna la sfârșit, indiferent de valoarea de pornire. Mai formal:

\forall n\in \mathbb {N} >0\ \exists i\in \mathbb {N} :(a_{0}=n\Rightarrow a_{i}=1).

{\ displaystyle \ forall n \ in \ mathbb {N}> 0 \ \ există i \ in \ mathbb {N}: (a_ {0} = n \ Rightarrow a_ {i} = 1).}

{\ displaystyle \ forall n \ in \ mathbb {N}> 0 \ \ există i \ in \ mathbb {N}: (a_ {0} = n \ Rightarrow a_ {i} = 1).}

Prin urmare, presupunerea ar fi falsă dacă ar exista o secvență care nu conține numărul 1; aceasta ar putea însemna un ciclu care se repetă fără a da vreodată 1 sau o succesiune nelimitată mai sus.

Uneori problema este afirmată diferit. Condiția de terminare (adică să se oprească dacă n = 1) este eliminată din conjectură, astfel încât secvența să nu se termine niciodată. Afirmând problema în acest fel, conjectura Collatz devine afirmația că secvența generată de algoritm ajunge întotdeauna la bucla infinită 1, 4, 2, 1, 4, 2 ...

Există o altă abordare pentru a defini conjectura, una care consideră să ruleze graficul Collatz de jos în sus. Acest grafic este definit de o „funcție inversă” a primei considerate:

R(n)={\begin{cases}\left\{2n,{\frac {n-1}{3}}\right\},&{\text{se }}n\equiv 4{\pmod {6}},\\\{2n\},&{\text{altrimenti.}}\end{cases}}

{\ displaystyle R (n) = {\ begin {cases} \ left \ {2n, {\ frac {n-1} {3}} \ right \} și {\ text {se}} n \ equiv 4 { \ pmod {6}}, \\\ {2n \} și {\ text {altfel.}} \ end {cases}}}

{\ displaystyle R (n) = {\ begin {cases} \ left \ {2n, {\ frac {n-1} {3}} \ right \} și {\ text {se}} n \ equiv 4 { \ pmod {6}}, \\\ {2n \} și {\ text {altfel.}} \ end {cases}}}

Studiind problema din această perspectivă, problema este definită în felul următor. Conjectura lui Collatz se reduce la două afirmații:

funcția inversă formează un copac , cu excepția ciclului 1-2-4;
toate numerele întregi sunt prezente în copac.

Argumente în favoarea acestuia

Deși conjectura nu a fost dovedită, majoritatea matematicienilor care s-au ocupat de ea consideră că presupunerea este adevărată. Să vedem câteva motive de susținere.

Dovezi experimentale

Conjectura a fost verificată (începând cu 2020) de către computer pentru toate valorile de până la $2^{68}\approx 10^{20,5}$ ${\ displaystyle 2 ^ {68} \ aproximativ 10 ^ {20,5}}$ ${\ displaystyle 2 ^ {68} \ aproximativ 10 ^ {20,5}}$ . ^[2] Intuitiv, ar fi surprinzător dacă cel mai mic contraexemplu ar fi suficient de mare pentru a depăși acest număr. Odată cu creșterea vitezei computerelor, vor fi verificate valori din ce în ce mai mari (în timp ce ne amintim că aceste teste nu vor dovedi niciodată corectitudinea conjecturii, ci doar posibila falsitate).

Considerații probabilistice

Dacă luăm în considerare doar numerele impare ale secvenței generate de algoritm, putem spune că, în medie, următorul număr impar ar trebui să fie egal cu aproximativ 3/4 din precedentul, ceea ce sugerează că, pe termen lung, acestea scad până la ajungând la 1.

Algoritmi pentru calcularea secvențelor Collatz

O secvență Collatz specifică poate fi calculată cu ușurință, după cum se arată în următorul exemplu de pseudocod:

 function collatz (n)
  în timp ce n> 1
    arată n
    dacă n ciudat
      setați n la 3n + 1
    altceva
      setați n la n / 2
  arată n

Sau, folosind recursivitatea :

 function collatz (n)
  arată n
  dacă n> 1
    dacă n ciudat
      colț (3n + 1)
    altceva
      colț (n / 2)

Aceste programe se termină când secvența ajunge la 1, pentru a evita imprimarea unei bucle infinite de 4, 2, 1. Dacă conjectura lui Collatz este adevărată, programele se termină întotdeauna, indiferent de numărul întreg pozitiv de pornire.

Optimizări

Dacă n este multiplu de 4, acesta poate fi împărțit la 4.

Motiv : inițial este uniform. Împărțit la două, este încă egal, deci poate fi împărțit la două a doua oară.

Mai general, în factorizarea înainte de n este posibilă înlocuirea puterii a două cu 2 ⁰ = 1.

Motiv : dacă puterea lui 2 în prima factorizare este mai mare decât 0, atunci numărul este par, iar la următorul punct vom avea aceeași factorizare cu 2 ridicat la o putere mai mică decât una. Repetând operația, ajungem la 2 ⁰ .

De exemplu : în loc de 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (17 pași), putem calcula 15, 46 (2 ¹ × 23), 23, 70 (2 ¹ × 35), 35, 106 (2 ¹ × 53), 53, 160 (2 ⁵ × 5), 5, 16 (2 ⁴ ), 1 (11 trepte ).

Dacă n este ciudat, puteți face (3 n + 1) / 2, omitând un pas.

Motiv : dacă n este impar, 3 n este, de asemenea, impar (produsul a două numere impare este întotdeauna impar) și 3 n + 1 este par, deci poate fi împărțit la două.

De exemplu : 3 × 35 + 1 = 106.

3 m + 1 face întotdeauna parte din secvența de 4 m + 1. Deci, dacă n ≡ 1 (mod 4), n poate fi convertit în ( n - 1) / 4 de câte ori este posibil, economisind câte un pas de fiecare dată . Numărul obținut, par sau impar, trebuie ulterior convertit în 3 n + 1.

Motiv: 4 m + 1 este întotdeauna impar, apoi devine 3 (4 m + 1) + 1 = 12 + 4 = 4 m (3 m + 1) și poate fi împărțit la patru.

De exemplu : 405 poate fi convertit ca: 405 → 101 → 25 → 6 → 19. Secvența normală Collatz conține și 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19.

Cele de mai sus pot fi utilizate pentru o nouă formulare, echivalentă cu cea anterioară, a funcției Collatz:

f(n)={\begin{cases}{\frac {n}{4}},&{\text{se }}n\equiv 0,\\3g(n)+1,&{\text{se }}n\equiv 1,\\{\frac {n}{2}},&{\text{se }}n\equiv 2,\\{\frac {1}{2}}(3n+1),&{\text{se }}n\equiv 3,\end{cases}}{\pmod {4}}

{\ displaystyle f (n) = {\ begin {cases} {\ frac {n} {4}} și {\ text {se}} n \ equiv 0, \\ 3g (n) +1 și & {\ text {se}} n \ equiv 1, \\ {\ frac {n} {2}} și {\ text {se}} n \ equiv 2, \\ {\ frac {1} {2}} (3n +1), și {\ text {se}} n \ equiv 3, \ end {cases}} {\ pmod {4}}}

{\ displaystyle f (n) = {\ begin {cases} {\ frac {n} {4}} și {\ text {se}} n \ equiv 0, \\ 3g (n) +1 și & {\ text {se}} n \ equiv 1, \\ {\ frac {n} {2}} și {\ text {se}} n \ equiv 2, \\ {\ frac {1} {2}} (3n +1), și {\ text {se}} n \ equiv 3, \ end {cases}} {\ pmod {4}}}

g(n)={\begin{cases}n,&{\text{se }}n\not \equiv 1,\\g({\frac {n-1}{4}}),&{\text{se }}n\equiv 1,\end{cases}}{\pmod {4}}

{\ displaystyle g (n) = {\ begin {cases} n și {\ text {se}} n \ not \ equiv 1, \\ g ({\ frac {n-1} {4}}) și {\ text {se}} n \ equiv 1, \ end {cases}} {\ pmod {4}}}

{\ displaystyle g (n) = {\ begin {cases} n și {\ text {se}} n \ not \ equiv 1, \\ g ({\ frac {n-1} {4}}) și {\ text {se}} n \ equiv 1, \ end {cases}} {\ pmod {4}}}

Notă istorică asupra diferitelor nume

La începutul anilor 1930, Lothar Collatz , student la Universitatea din Hambourg, era implicat în teoria numerelor și teoria graficelor. A început cu un număr întreg pozitiv, i-a aplicat un algoritm iterativ, a reprezentat graficele asociate și și-a pus întrebări care încă nu au răspuns.

Matematicianul german Helmut Hasse, un prieten al lui Collatz, a răspândit problema cunoscută și sub numele de algoritmul Hasse sau problema 3x + 1 .

Deoarece Hasse a prezentat problema în anii 1950 în timpul unei vizite la Universitatea Syracuse (lângă New York), el a propus să o numească problema Syracuse .

Matematicianul polonez Stanislaw Ulam a distribuit algoritmul la Universitatea din Los Alamos, unde a lucrat în timpul celui de-al doilea război mondial. Acesta este motivul pentru care problema este cunoscută și sub numele de problema Ulam .

În anii 1960 S. Kakutani a devenit din nou interesat de această problemă, iar conjectura a luat numele de „ problema Kakutani ”.

În cultura de masă

Conjectura Collatz este citată:

în filmul Femeia care cântă de Jeanne Marwan în timpul unei lecții de matematică la Universitate;
în romanul Ultima teoremă de Arthur C. Clarke.

Notă

^ Gūnter M. Ziegler, Să dăm numerele? Orme Edizioni, 2011, p.116
^ Despre problema 3x + 1 , pe ericr.nl . Adus la 6 ianuarie 2018 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre Conjectura lui Collatz

linkuri externe

( EN ) Jeff Lagarias: Problema 3x + 1 și generalizările sale , American Mathematical Monthly Volume 92, 1985, pp. 3 - 23.
(EN) Eric W. Weisstein, Collatz Problem in MathWorld Wolfram Research.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Gūnter M. Ziegler, Să dăm numerele? Orme Edizioni, 2011, p.116

[2] Despre problema 3x + 1 , pe ericr.nl . Adus la 6 ianuarie 2018 .

[1]

[2]