Tekst źródłowy strony Problem Collatza

'''Problem Collatza''' (znany też jako '''problem 3x+1''', '''problem Ulama''', '''problem Kakutaniego''', '''problem syrakuzański''') – nierozstrzygnięty dotychczas problem o wyjątkowo prostym – jak wiele innych problemów [[teoria liczb|teorii liczb]] – sformułowaniu. Nazwa pochodzi od nazwiska niemieckiego matematyka [[Lothar Collatz|Lothara Collatza]] (1937). Zagadnienie to było również rozpatrywane przez polskiego matematyka [[Stanisław Ulam|Stanisława Ulama]], a także przez [[Shizuo Kakutani]]ego.

== Sformułowanie problemu Collatza ==
Weźmy dowolną dodatnią [[Liczby naturalne|liczbę naturalną]] <math>c_0.</math> Jeśli jest ona [[parzystość liczb|parzysta]], to niech <math>c_1 = c_0/2,</math> w przeciwnym wypadku niech <math>c_1 = 3c_0 + 1.</math> Następnie z liczbą <math>c_1</math> postępujemy podobnie jak z <math>c_0</math> i kontynuujemy ten proces. Otrzymamy w ten sposób [[ciąg (matematyka)|ciąg]] liczb naturalnych określony [[rekurencja|rekurencyjnie]] przez formułę
:: <math>c_{n+1} = \begin{cases}
  \frac{1}{2}c_n & \text{gdy } c_n \text{ jest parzysta} \\
  3c_n + 1       & \text{gdy } c_n \text{ jest nieparzysta}
\end{cases}</math>

lub
:: <math>c_{n+1} = \frac{1}{2}c_n - \frac{1}{4}(5c_n+2)((-1)^{c_n}-1).</math>

Przedmiotem problemu jest przypuszczenie, że niezależnie od jakiej liczby <math>c_0</math> wystartujemy, w końcu dojdziemy do liczby 1.

Zdefiniowany wyżej ciąg jest ciągiem nieskończonym i łatwo zauważyć, że jeśli pewien wyraz tego ciągu jest równy 1, to następne po nim wyrazy będą równe 4, 2, 1, 4, 2, 1,... O takim ciągu mówimy, że wpada w cykl (w pętlę).

Przypuszczenie można więc sformułować inaczej: niezależnie od jakiej liczby <math>c_0</math> wystartujemy, to ciąg wpadnie w cykl (4, 2, 1).

== Przykłady ==
[[Plik:Syracuse15.png|thumb|200px|Diagram dla ciągu zaczynającego się od 15]]
[[Plik:Collatz-graph-all-30-no27.svg|thumb|200px|Graf pierwszych 30 liczb naturalnych (bez 27).]]
* Zaczynając od <math>c_0</math> = 11, mamy:
:: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

* Zaczynając od <math>c_0</math> = 15, mamy:
:: 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

* Zaczynając od <math>c_0</math> = 27, mamy:
:: 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.

tutaj cały proces wymaga aż 111 kroków z maksymalną osiągniętą wartością 9232.

== Próby rozstrzygnięcia problemu Collatza ==
Wykazano prawdziwość hipotezy Collatza dla liczb <math>c_0</math> mniejszych niż 20 × 2<sup>58</sup>&nbsp;≈&nbsp;5.764{{e|18}}{{odn|Lagarias|2010|s=189}}.

Każdy ciąg nieskończony {c<sub>n</sub>} startujący od pewnej liczby naturalnej dodatniej ma następującą własność:
: ciąg {c<sub>n</sub>} jest ograniczony wtedy i tylko wtedy, gdy wpada w pewien cykl.

Rzeczywiście, jeśli ciąg wpada w jakiś cykl, to jest tylko skończona liczba początkowych wyrazów niewchodzących do tego cyklu. Odwrotnie, jeśli ciąg jest ograniczony, to nieskończona liczba wyrazów ciągu osiąga jedynie skończoną liczbę wartości, co oznacza, że niektóre wyrazy muszą się powtarzać. A ponieważ w ciągu {c<sub>n</sub>} każdy wyraz zależy jedynie od swojego bezpośredniego poprzednika, więc wyrazy powtarzające się wyznaczają początek i koniec pewnego cyklu.

Ponadto
: jeśli ciąg {c<sub>n</sub>} jest nieograniczony, to jest rozbieżny do nieskończoności.

Rzeczywiście, przypuśćmy, że ciąg nie jest rozbieżny do nieskończoności. Stąd dla pewnej liczby naturalnej <math>N</math> istnieje nieskończenie wiele wyrazów ciągu {c<sub>n</sub>} mniejszych od <math>N,</math> co oznacza, że pewne dwa z nich mają te same wartości, tym samym wyznaczają one pewien cykl. Stąd z kolei wynika, że ciąg jest ograniczony, wbrew założeniu.

Z powyższego wynika, że są tylko dwie możliwości zaprzeczenia hipotezie:
* dla jakiejś liczby początkowej {c<sub>0</sub>} otrzymany ciąg {c<sub>n</sub>} jest ograniczony i wpada w cykl ''inny'' niż (4, 2, 1);
* dla jakiejś liczby początkowej {c<sub>0</sub>} otrzymany ciąg {c<sub>n</sub>} jest nieograniczony, czyli jest rozbieżny do nieskończoności.

[[Paul Erdős]] wypowiedział{{odn|Lagarias|1985|s=3}} o problemie Collatza słynne zdanie: „''mathematics is not yet ready for such problems''” – „matematyka nie jest jeszcze gotowa na takie problemy”. Niewątpliwie świadczy to o złożoności ewentualnego rozwiązania, z drugiej strony kontrast pomiędzy ową złożonością a prostotą sformułowania jest intrygujący.

== Uogólnienie problemu Collatza wszystkie liczby całkowite<ref>{{Cytuj |autor = Eric W. Weisstein |tytuł = Collatz Problem |data dostępu = 2024-02-21 |opublikowany = Wolfram MathWorld |url = https://mathworld.wolfram.com/CollatzProblem.html |język = en}}</ref> ==
Przy założeniu, że ciąg możemy zacząć także od zera lub liczby ujemnej, znaleziono dotąd kolejne trzy cykle (poza trywialnym cyklem składającym się tylko z zera), w które może on wpaść:
* −1, −2, −1,
* −5, −14, −7, −20, −10, −5,
* −17, −50, −25, −74, −37, −110, −55, −164, −82, −41, −122, −61, −182, −91, −272, −136, −68, −34, −17.

== Cykle ''n''-tego stopnia ==
W 1978 roku R. Steiner oraz w 1996 i 2002 roku J. Simons i B. de Weger (bazując na metodzie Steinera) udowodnili, że pewne rodzaje cykli nie mogą istnieć.

Aby to wyjaśnić, zdefiniujmy transformację dla [[Liczby całkowite|liczb całkowitych]] dodatnich <math>a</math> i <math>b</math> oraz <math>A{:}</math>
   b = T(a;A)   ''znaczy''   b = (3*a+1)/2^A

: gdzie <math>A</math> to maksymalna potęga liczby <math>2^A,</math> która dzieli liczbę <math>b</math> bez reszty
   ''Przykład:''
   a = 15, ''wtedy'' b = T(15,A)  3*15+1 = 46, ''więc'' A = 1   b = (3*15+1)/2^1 = 23
   23 = T(15;1)

* Określmy [[Konkatenacja|konkatenację]] (rozszerzalną do dowolnej długości):
   b = T(T(a;A);B) = T(a;A,B)

   ''Przykład:''
   b = T(15;A,B) = T(15;1,1) = ((3*15+1)/2^1*3+1)/2^B = (3*23+1)/2^B = 70/2^1 = 35
   35 = T(15;1,1)

* Zdefiniujmy transformację, dla której mamy <math>L</math> wykładników równych <math>1</math> i ostatni <math>A</math> większy od liczby <math>1{:}</math>
   b = T(a;1,1,1,1,1,...,1,A) = T(a;(1)<sub>L</sub>,A)

: przy czym liczba <math>L</math> może być dowolnie duża
   ''Przykład:''
   b = T(15;1,1,1,A) = T(15;(1)<sub>3</sub>,A) = (53*3+1)/2^A = 160/2^5 = 5
   5 = T(15;(1)<sub>3</sub>,5)

* Wówczas funkcja:
   b = T(a;(1)<sub>L</sub>,A)

gdzie <math>b = a</math> to '''cykl I stopnia''' o długości <math>N = L + 1</math> [[iteracja|iteracji]].

=== Twierdzenia ===
* Ray Steiner udowodnił w 1978 r., że nie istnieje cykl I stopnia. Oznacza to, że niezależnie od tego, ile iteracji <math>L</math> zostanie wykonanych oraz ile będzie wynosił wykładnik <math>A,</math> zaczynając od liczby <math>a,</math> nigdy nie otrzymamy liczby <math>b=a.</math>
* w 1996 r. John Simons (opierając się na metodzie Steinera) udowodnił, iż nie istnieje cykl II stopnia: ''a&nbsp;=&nbsp;T(a;(1)<sub>L</sub>,A,(1)<sub>M</sub>,B)'', niezależnie od tego ile będzie wynosić <math>L</math> oraz <math>M.</math>
* w 2002 r. John Simons oraz Benne de Weger wykazali, że nie istnieje cykl mniejszy lub równy cyklowi 68. stopnia: ''a&nbsp;=&nbsp;T(a;(1)<sub>L1</sub>,A<sub>1</sub>,(1)<sub>L2</sub>,A<sub>2</sub>,...,(1)<sub>L68</sub>,A<sub>68</sub>)''.
* w 2002 r. John Simons oraz Benne de Weger wykazali także, że nie istnieje cykl większy o kilka wartości od cyklu 68. stopnia (szacując to na podstawie poprzedniego wyniku).

== Hipoteza Collatza w ujęciu diofantycznym ==
Warunki hipotezy można ująć za pomocą pewnych [[Równanie diofantyczne|równań diofantycznych]]. Aby to wyjaśnić posłużymy się pewną skróconą formułą opisującą ciąg.

=== Skrócona formuła rekurencyjna ===
Każdą operację typu <math>3 \cdot x+1</math> w ciągu Collatza wykonywaną zgodnie z definicją na nieparzystym <math>x</math> można skrócić do postaci <math>\tfrac{3 \cdot x+1}{2},</math> gdyż liczba <math>3 \cdot x+1</math> jest zawsze parzysta (przy nieparzystym <math>x</math>), a zatem zawsze w następnej kolejności wywołuje dzielenie przez <math>2.</math> Dlatego ciąg Collatza możemy równoważnie zdefiniować za pomocą następującej skróconej formuły:
:: <math>c_{n+1} = \begin{cases}
  \frac{1}{2} \cdot c_n               & \text{gdy } c_n \text{ jest parzysta} \\
  \frac{3}{2} \cdot c_n + \frac{1}{2} & \text{gdy } c_n \text{ jest nieparzysta}
\end{cases}.</math>

=== Przykłady ===
* Zaczynając od <math>n</math> = 7, mamy:
: 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1.

* Zaczynając od <math>n</math> = 15, mamy:
: 15, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.

== Ciąg Collatza w ujęciu diofantycznym ==
Obserwując zachowanie się skróconego ciągu dla określonych liczb, można zauważyć, iż niektóre liczby nieparzyste wywołują kilka operacji typu <math>1{,}5 \cdot x+0{,}5</math> z rzędu – do momentu, gdy zostanie osiągnięta liczba parzysta, inne natomiast tylko jedną. Liczby te można zapisać przy użyciu dwóch naturalnych zmiennych <math>a</math> oraz <math>k</math> warunkujących wielkość danej liczby oraz liczba powtarzalnych operacji typu <math>1{,}5 \cdot x+0{,}5,</math> które dana liczba determinuje za pomocą następującego wyrażenia:
:: <math>2^a \cdot k-1.</math>

Przy czym zmienna <math>a</math> jest determinantą '''liczby''' następujących po sobie operacji typu <math>1{,}5 \cdot x+0{,}5,</math> natomiast <math>k</math> tylko '''wielkości''' liczby. Każda liczba postaci <math>2^a \cdot k-1</math> generuje w ciągu Collatza po <math>a</math> operacjach liczbę postaci:
:: <math>3^a \cdot k-1.</math>

Weźmy np. liczbę 15:
:: <math>15 = 2^3 \cdot 2-1,</math> a zatem liczba, która następuje po niej po <math>a=3</math> operacjach wynosi <math>3^3 \cdot 2-1 = 53,</math>

jednak liczbę 15 można również zapisać następująco:
:: <math>15 = 2^4 \cdot 1-1,</math> wtedy jej następnik po <math>a=4</math> operacjach wyniesie: <math>3^4 \cdot 1-1 = 80.</math>

Obie konstatacje są poprawne, ale tylko gdy zapiszemy liczbę <math>2^a \cdot k-1</math> tak, iż współczynnik <math>k</math> będzie '''nieparzysty''' otrzymamy ostatnią parzystą składową ciągu operacji typu <math>1{,}5 \cdot x+0{,}5.</math> Bazując na powyższym zapisie, możemy zdefiniować ciąg jeszcze ogólniej, ujmując powtarzalne dzielenie liczb parzystych przez liczbę 2 potęgowo:
:: <math>2^a \cdot k-1 \to (3^a \cdot k-1)/2^p \to 2^c \cdot d-1 \to (3^c \cdot d-1)/2^q \to 2^e \cdot f-1 \to (3^e \cdot f-1)/2^i \to 2^n \cdot m-1 \to...</math>

=== Przykłady ===
* Zaczynając od <math>n</math> = 21, mamy:
:: <math>2^1 \cdot 11-1 \to (3 \cdot 11-1)/2^5 \to 2^1 \cdot 1-1 \to...</math>

* Zaczynając od <math>n</math> = 7, mamy:
:: <math>2^3 \cdot 1-1 \to (3^3 \cdot 1-1)/2^1 \to 2^1 \cdot 7-1 \to (3^1 \cdot 7-1)/2^2 \to 2^1 \cdot 3-1 \to (3^1 \cdot 3-1)/2^3 \to 2^1 \cdot 1-1 \to...</math>

== Cykl w ujęciu diofantycznym ==
Warunkiem powstania cyklu w ciągu Collatza jest zajście równości pomiędzy pierwszym a <math>n</math>-tym wyrazem ciągu. Musi być spełnione zatem jedno z równań:
:: <math>2^a \cdot k-1 = \tfrac{3^a \cdot k-1}{2^p}</math>

lub
:: <math>2^a \cdot k-1 = \tfrac{3^c \cdot d-1}{2^q}</math>

lub
:: <math>2^a \cdot k-1 = \tfrac{3^e \cdot f-1}{2^i}</math>

itd.

Przy czym, jeżeli na przykład:
:: <math>\tfrac{3^e \cdot f-1}{2^a \cdot k-1} = 2^i,</math>

to naturalnie spełnione muszą być również równania:
:: <math>\tfrac{3^a \cdot k-1}{2^c \cdot d-1} = 2^p</math>

oraz
:: <math>\tfrac{3^c \cdot d-1}{2^e \cdot f-1} = 2^q.</math>

Ogólnie w zależności od długości cyklu rozważamy zatem układ <math>n</math>-tego typu równań (poniżej <math>n=3</math>):
:: <math>\begin{cases}
  \tfrac{3^e \cdot f-1}{2^a \cdot k-1} = 2^i \\
  \tfrac{3^a \cdot k-1}{2^c \cdot d-1} = 2^p \\
  \tfrac{3^c \cdot d-1}{2^e \cdot f-1} = 2^q
\end{cases}.</math>

Każdy taki układ po uporządkowaniu daje się zapisać jako iloczyn następujących czynników:
:: <math>\tfrac{3^a \cdot k-1}{2^a \cdot k-1} \cdot \tfrac{3^c \cdot d-1}{2^c \cdot d-1} \cdot \tfrac{3^e \cdot f-1}{2^e \cdot f-1} = 2^x.</math>

Potęgi dwójek skracają się do postaci <math>2^x.</math> Warunek jakiegokolwiek cyklu będzie zatem następującym równaniem diofantycznym:
:: <math>\tfrac{3^a \cdot k-1}{2^a \cdot k-1} \cdot \tfrac{3^c \cdot d-1}{2^c \cdot d-1} \cdot \tfrac{3^e \cdot f-1}{2^e \cdot f-1} \cdot \ldots \cdot \tfrac{3^n \cdot m-1}{2^n \cdot m-1} = 2^x.</math>

Przy czym liczba ilorazowych czynników iloczynu może być dowolna, a wszystkie zmienne to liczby naturalne.

* Powyższy <math>n</math>-czynnikowy iloczyn jest tożsamy z cyklem <math>n</math>-tego stopnia. Mają tu zastosowanie zatem [[Twierdzenie Steinera (mechanika)|twierdzenia Steinera]], Simonsa oraz de Wegera (o których mowa w punkcie 5.1). Hipotetycznie, gdyby istniało rozwiązanie równania dla <math>n</math> czynników, moglibyśmy mówić o istnieniu pętli <math>n</math>-tego stopnia (pomijamy tu przypadek pętli trywialnej).

=== Przykład ===
Pętla trywialna:
:: <math>\tfrac{3^1 \cdot 1-1}{2^1 \cdot 1-1} \cdot \tfrac{3^1 \cdot 1-1}{2^1 \cdot 1-1} \cdot \tfrac{3^1 \cdot 1-1}{2^1 \cdot 1-1} \cdot \ldots \cdot \tfrac{3^1 \cdot 1-1}{2^1 \cdot 1-1} = 2^x.</math>

== Problem rozbieżności do nieskończoności w ujęciu diofantycznym ==
Bazując na przedstawionym zapisie diofantycznym, możemy zdefiniować również warunek rozbieżności do nieskończoności ciągu Collatza. Pewność, że ciąg dla danej liczby nie jest rozbieżny do nieskończoności, daje nam zapętlanie się tej liczby (co zostało rozważone powyżej), wpadanie liczby w pętlę lub wystąpienie w ciągu liczby 1 (po skończonej liczbie iteracji), co również jest szczególnym przypadkiem wpadania liczby w pętlę trywialną. Pomijając przypadki hipotetycznych pętli (innych niż 1, 2, 1,...), ciąg Collatza dla dowolnej nierozbieżnej do nieskończoności liczby początkowej <math>2^a \cdot k-1</math> można zapisać jako następujący skończony iloczyn:
:: <math>\tfrac{2^a \cdot k-1}{1} \cdot \tfrac{3^a \cdot k-1}{2^a \cdot k-1} \cdot \tfrac{3^c \cdot d-1}{2^c \cdot d-1} \cdot \tfrac{3^e \cdot f-1}{2^e \cdot f-1} \cdot \ldots \cdot \tfrac{3^n \cdot m-1}{2^n \cdot m-1} = 2^x.</math>

Wynika to z tego, iż wszystkie czynniki w takim iloczynie z racji relacji, jaka między nimi zachodzi, skracają się wzajemnie do postaci potęgi liczby dwa, poza licznikiem ostatniego czynnika, który sam musi być [[Potęga dwójki|potęgą dwójki]] (co ''de facto'' gwarantuje wystąpienie liczby 1), aby równanie mogło być spełnione. Jeżeli dla jakiejś liczby początkowej licznik następujący po skończonej liczbie operacji nie będzie potęgą liczby 2, bo ciąg nigdy nie osiągnie liczby 1 lub osiąga ją w nieskończoności, nie jest możliwe skonstruowanie skończonego iloczynu spełniającego równanie. Próba rozstrzygnięcia problemu w tej drodze powinna zatem skutkować dowodem, że iloczyn spełniający powyższe równanie dla dowolnej liczby <math>2^a \cdot k-1</math> będzie <u>skończony</u>.

=== Przykłady ===
* Zaczynając od 9, mamy:
:: <math>\tfrac{2^1 \cdot 5-1}{1} \cdot \tfrac{3^1 \cdot 5-1}{2^1 \cdot 5-1} \cdot \tfrac{3^3 \cdot 1-1}{2^3 \cdot 1-1} \cdot \tfrac{3^1 \cdot 7-1}{2^1 \cdot 7-1} \cdot \tfrac{3^1 \cdot 3-1}{2^1 \cdot 3-1} = 2^7.</math>

* Zaczynając od 21, mamy:
:: <math>\tfrac{2^1 \cdot 11-1}{1} \cdot \tfrac{3^1 \cdot 11-1}{2^1 \cdot 11-1} = 2^5.</math>

== Uogólnienie równań na liczby ujemne ==
Warunki hipotezy można ująć za pomocą równań diofantycznych również dla [[Znak liczby|liczb ujemnych]]. W owych równaniach zmieniamy wtedy tylko znaki „<math>-</math>” przed jedynkami na „+”. Warunek cyklu zapiszemy zatem jako następujące równanie:
:: <math>\tfrac{3^a \cdot k+1}{2^a \cdot k+1} \cdot \tfrac{3^c \cdot d+1}{2^c \cdot d+1} \cdot \tfrac{3^e \cdot f+1}{2^e \cdot f+1} \cdot \ldots \cdot \tfrac{3^n \cdot m+1}{2^n \cdot m+1} = 2^x.</math>

Natomiast warunek rozbieżności do nieskończoności dla dowolnej liczby ujemnej przyjmie postać:
:: <math>\tfrac{2^a \cdot k+1}{1} \cdot \tfrac{3^a \cdot k+1}{2^a \cdot k+1} \cdot \tfrac{3^c \cdot d+1}{2^c \cdot d+1} \cdot \tfrac{3^e \cdot f+1}{2^e \cdot f+1} \cdot \ldots \cdot \tfrac{3^n \cdot m+1}{2^n \cdot m+1} = 2^x.</math>

=== Przykłady ===
Trzy znane pętle dla liczb ujemnych w ciągu Collatza reprezentują następujące równania:

* Zaczynając od liczby −1, mamy:
:: <math>\tfrac{3^1 \cdot 0+1}{2^1 \cdot 0+1} \cdot \tfrac{3^1 \cdot 0+1}{2^1 \cdot 0+1} \cdot \tfrac{3^1 \cdot 0+1}{2^1 \cdot 0+1} \cdot \ldots \cdot \tfrac{3^1 \cdot 0+1}{2^1 \cdot 0+1} = 2^x.</math>

* Zaczynając od liczby −5, mamy:
:: <math>\tfrac{3^2 \cdot 1+1}{2^2 \cdot 1+1} = 2^1.</math>

* Zaczynając od liczby −17, mamy:
:: <math>\tfrac{3^4 \cdot 1+1}{2^4 \cdot 1+1} \cdot \tfrac{3^3 \cdot 5+1}{2^3 \cdot 5+1} = 2^4.</math>

== Liczby postaci 3n jako liczby, które się nie zapętlają ==
Dla dowolnej liczby <math>2^a \cdot k-1,</math> która zapętla się w ciągu Collatza istnieje nieskończenie wiele jej następników oraz poprzedników. Przykładowo w cyklu trywialnym po liczbie jeden następuje nieskończenie wiele jej następników, jednak możemy wyznaczyć również równie wiele jej poprzedników. Hipotetycznie, zgodnie z zapisem diofantycznym ciągu Collatza poprzednikiem dowolnej liczby <math>2^a \cdot k-1</math> będzie zawsze jakaś liczba:
:: <math>3^p \cdot r - 1 = 2^t \cdot (2^a \cdot k-1).</math>

Jednakże gdy liczba <math>2^a \cdot k-1</math> jest postaci <math>3n,</math> to równanie diofantyczne:
:: <math>3^p \cdot r - 1 = 2^t \cdot 3n.</math>

Nie może być spełnione dla żadnej liczby <math>2^a \cdot k-1,</math> ponieważ prawa strona równania dzieli się przez 3 bez reszty, natomiast lewa nie. Oznacza to, iż żadna liczba postaci <math>3n</math> nie ma poprzednika w ciągu Collatza, a zatem nie może spełniać również warunków pętli.

== Uogólnienie problemu 3x+1 ==
Ogólnie każdy ciąg zdefiniowany dowolnym '''skończonym''' ciągiem [[Arytmetyka elementarna|działań arytmetycznych]] dla liczby nieparzystej oraz '''redukcją''' liczby parzystej do liczby nieparzystej poprzez dzielenie jej przez liczbę 2 daje się zapisać za pomocą podobnych jak w ciągu Collatza równań diofantycznych. Przy czym zależność pomiędzy definicją ciągu a pojedynczym wyrażeniem diofantycznym jest następująca:
:: <math>c_{k+1} = \begin{cases}
  \tfrac{1}{2} \cdot c_k                            & \text{gdy } c_k \text{ jest parzysta} \\
  \tfrac{n}{m} \cdot c_k + \tfrac{(n-m) \cdot b}{m} & \text{gdy } c_k \text{ jest nieparzysta}
\end{cases} \quad \Rightarrow \quad \tfrac{n^a \cdot i-b}{m^a \cdot i-b}.</math>

=== Przykłady ===
* Weźmy ciąg zdefiniowany następująco:
:: <math>c_{k+1} = \begin{cases}
  \frac{1}{2} \cdot c_k                          & \text{gdy } c_k \text{ jest parzysta} \\
  (c_k \cdot \tfrac{3}{5}+6) \cdot \tfrac{7}{13} & \text{gdy } c_k \text{ jest nieparzysta}
\end{cases}.</math>

Pierwszym krokiem będzie wyznaczenie wielkości <math>n</math> oraz <math>m,</math> dopiero potem <math>b,</math> jednak kolejność nie ma tu znaczenia, należy zachować tylko jedną zasadę: aby wyrażenie faktycznie opisywało ciąg wielkości <math>n</math> oraz <math>m</math> muszą być dobrane tak aby iloraz <math>\tfrac{n}{m}</math> był ułamkiem '''nieskracalnym''':
:: <math>(c_k \cdot \tfrac{3}{5}+6) \cdot \tfrac{7}{13} = c_k \cdot \tfrac{21}{65} + \tfrac{42}{13}.</math>

Zatem:
:: <math>\tfrac{n}{m} = \tfrac{21}{65}.</math>

Natomiast:
:: <math>\tfrac{(n-m) \cdot b}{m} = \tfrac{(21-65) \cdot b}{65},</math>

:: <math>b = \tfrac{1365}{286}.</math>

Nasze wyrażenie przyjmuje więc postać:
:: <math>\tfrac{21^a \cdot i - \tfrac{1365}{286}}{65^a \cdot i - \tfrac{1365}{286}}.</math>

Możemy na tej podstawie skonstruować również warunki zapętlania się ciągu oraz rozbieżności do nieskończoności.
* Rozważmy jeszcze inny ciąg:
:: <math>c_{k+1} = \begin{cases}
  \frac{1}{2} \cdot c_k   & \text{gdy } c_k \text{ jest parzysta} \\
  2{,}5 \cdot c_k + 1{,}5 & \text{gdy } c_k \text{ jest nieparzysta}
\end{cases}.</math>

Nasze wyrażenie przyjmuje wtedy następującą postać:
:: <math>\tfrac{5^a \cdot i-1}{2^a \cdot i-1}.</math>

Taki ciąg zapętla się już dla niewielkich liczb. Na przykład dla liczby 3:
:: <math>\tfrac{5^2 \cdot 1-1}{2^2 \cdot 1-1} = 2^3.</math>

Pętla występuje też dla liczby 39:
:: <math>\tfrac{5^3 \cdot 5-1}{2^3 \cdot 5-1} = 2^4.</math>

== Związek z problemem stopu ==
{{zobacz też|problem stopu}}
Algorytm sprawdzający hipotezę Collatza dla zadanej liczby naturalnej <code>x</code> można przedstawić w postaci [[pseudokod]]u w następujący sposób:
<syntaxhighlight lang="Pascal">
  procedure collatz(x);
  begin
    do
      if x mod 2 = 0 then
        x := x / 2
      else
        x := 3 * x + 1
    while x <> 1
  end
</syntaxhighlight>Program w C++ i standardowym wyjściem STD wypisujący wszystkie liczby z podaniem największej z nich i liczby powtórzeń<syntaxhighlight lang="c++" line="1" start="0">
#include <iostream>

using namespace std;

int main()
{
    long long int I = 0;
    int l = 0;
    long long int x = 0;
    do{
    I = 0;
    l = 0;
    x = 0;
    cin >> I;

    while(I != 1){
        if(I % 2 == 0){
             I = I/2;
        }else{
            I = (I*3)+1;
        }
        if(x < I){
            x = I;
        }
        l++;
        cout << I << endl;
    }
    cout << "MAX: " << x << " repeats: " << l << endl;
    }while(true);
    return 0;
}

</syntaxhighlight>Problem Collatza jest prawdopodobnie niealgorytmiczny, tzn. prawdopodobnie nie istnieje algorytm pozwalający rozstrzygnąć hipotezę{{fakt|data=2012-11}}. Z przypuszczalnej niealgorytmiczności problemu wynika między innymi to, iż nie wiadomo, czy przedstawiona wyżej procedura <code>collatz</code> zatrzyma się w skończonym czasie – pytanie o własność stopu tego programu pozostaje otwarte.

Wiele osób{{fakt|data=2012-05}} zaangażowanych w program [[Berkeley Open Infrastructure for Network Computing|BOINC]] uczestniczyło w projekcie [[3x+1@home]], którego celem było rozwiązanie tego problemu poprzez znalezienie kontrprzykładu. Obecnie na stronie tego zamkniętego projektu można znaleźć listę liczb-kandydatów użytych w projekcie, dla których długość ciągu przed osiągnięciem pętli {4, 2, 1} wyniosła 1000 iteracji.

Kontynuacją zakończonego projektu 3x+1@home jest [[Collatz Conjecture]] również wykorzystujący infrastrukturę [[Berkeley Open Infrastructure for Network Computing|BOINC]].

* [[b:Kody źródłowe/Problem Collatza|zobacz program prezentujący problem Collatza]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę |nazwisko=Lagarias |imię=Jeffrey C. |tytuł=The Ultimate Challenge: The 3x+1 Problem |url=https://books.google.com/books?hl=pl&lr=&id=hekJ7JDMEVkC&oi=fnd&pg=PA189&dq=%2220+%C3%97+258%22+3n+%2B1+problem&ots=67SURDBgT0&sig=LdOUhyOw6ZYO1wtXToP12yeoYtk&redir_esc=y#v=onepage&q=%2220%20%C3%97%20258%22%203n%20%2B1%20problem&f=false |wydawca=American Mathematical Society |miejsce=Providence |rok=2010 |isbn=978-0-8218-4940-8 |język=en |odn=tak}}
* {{cytuj pismo |nazwisko=Lagarias |imię=Jeffrey C. |tytuł=The 3x+1 Problem and Its Generalizations |url=http://www.gotarzj.amc8.org/sites/default/files/pdf/upload_library/22/Ford/Lagarias3-23.pdf |czasopismo=American Mathematical Monthly |wydanie=92 |strony=3–23 |rok=1985 |issn=0002-9890 |język=en |odn=tak}}

== Linki zewnętrzne ==
* {{MathWorld|adres=CollatzProblem |tytuł=Collatz Problem |data dostępu=12 grudnia 2020}}
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Syracuse_problem Syracuse problem]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
* [http://go.helms-net.de/math/collatz/Collatz061102.pdf Collatz cycles? (pdf)] {{lang|en}}
* [http://go.helms-net.de/math/collatz/aboutloop/collloopintro_main.htm Collatz cycles] {{lang|en}}
* [http://www.matifutbol.com/en/blackhole.html#collatz Problem Collatz i inne czarne dziury] {{lang|en}}
* [https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Lagarias3-23.pdf The 3x+1 problem and its generalizations (pdf)] {{lang|en}}

{{Teoria liczb}}
{{Ciągi liczbowe}}

[[Kategoria:Otwarte problemy teorii liczb]]
[[Kategoria:Hipotezy w teorii liczb]]