Matematyka.pl

Ostatnio natknąłem się na Problem Collatza, według Wikipedii nierozstrzygnięty dotychczas problem, który pyta, czy ciąg zadany rekurencyjnie:
\(\displaystyle{ c_{n+1}=\begin{cases} \frac{c_{n}}{2} , c_{n}=0 (\bmod2) \\3c_{n}+1, c_{n}=1 (\bmod2) \end{cases} }\)
zawsze wpadnie w pętlę 4,2,1 niezależnie od wyboru \(\displaystyle{ c_{0}}\). I dowód wydaje mi się absolutnie banalny, \(\displaystyle{ c_{n}}\) może być w jednej z czterech postaci: \(\displaystyle{ 4k; 4k+1; 4k+2; 4k+3}\) dla pewnej liczby całkowitej \(\displaystyle{ k}\). I dla każdej możliwości prześledźmy co się dzieje w kolejnych krokach:
\(\displaystyle{ 4k \rightarrow 2k}\)
\(\displaystyle{ 4k+1 \rightarrow 12k+4 \rightarrow 6k+2 \rightarrow 3k+1}\)
\(\displaystyle{ 4k+2 \rightarrow 2k+1}\)
\(\displaystyle{ 4k+3 \rightarrow 12k+10 \rightarrow 6k+5 \rightarrow 12k+16 \rightarrow 6k+8 \rightarrow 3k+4}\)
I zauważmy, że dla każdego przypadku na po skończonej liczbie kroków uzyskaliśmy liczbę ostro mniejszą niż wyjściowa (ponieważ \(\displaystyle{ k>1}\). A skoro startujemy od dowolnej liczby całkowitej więc w skończonej liczbie kroków dojdziemy do 1 więc wpadniemy w cykl. Co więcej sam problem Collatza jest częścią zadania 1 z 67 OM więc pytanie, czy ja czegoś nie rozumiem w sformułowaniu problemu czy to że jest to problem otwarty to błąd powielany w wielu miejscach po prostu?

ale np.\(\displaystyle{ 6 \rightarrow 3 \rightarrow 10 \rightarrow}\) .... itd

dla każdego przypadku na po skończonej liczbie kroków uzyskaliśmy liczbę ostro mniejszą niż wyjściowa

Papabile pisze: 30 gru 2022, o 08:26\(\displaystyle{ 4k+3 \rightarrow 12k+10 \rightarrow 6k+5 \rightarrow 12k+16 \rightarrow 6k+8 \rightarrow 3k+4}\)

Tu masz błąd, powinno być

\(\displaystyle{ 4k+3 \rightarrow 12k+10 \rightarrow 6k+5 \rightarrow \red{18k+16} \rightarrow...}\)

JK

Według mnie prawdopobnie to jest sednem dowodu, że ciąg Collatza jest "zbieżny". Moje amatorskie rozmyślania na ten temat są tutaj:

Problem Collatza to piękny przykład jak perspektywa patrzenia na problem jak chaos pojedynczych ciągów zamienia się w porządek gdy patrzymy globalnie czyli na wszystkie ciągi.Istota problemu to konflikt parzystych z nieparzystymi, który jak głosi hipoteza kończy się zwycięstwem parzystych. Dlaczego? Spróbuję to w skrócie wyjaśnić. Sukces lub porażka parzystych zależy od dwóch czynników. Pierwszy z nich to skuteczność pojedynczej liczby. Tutaj górą nieparzyste, bo każda z nich zwiększa kolejny wyraz o 3 razy plus 1 gdy tymczasem parzyste zmniejszają 2-krotnie, co w pojedynku 1 na 1 daje wzrost ok.1,5 raza. Drugi czynnik, jak się okazuje kluczowy to liczebność parzystych i nieparzystych we wszystkich ciągach Collaza. Jeśli ktoś chciałby się zabawić i wykorzystując sztuczną inteligencje niech wygeneruje na początek 64 początkowe ciągi ale tylko z 6 początkowymi wyrazami a następnie liczby parzyste zastąpi literką p a nieparzyste n. Otrzymacie tablicę 64x6 . Czytając po kolumnach zauważycie że literki układają się w cykle, co pozwoli obliczyć stosunek parzystych do nieparzystych dla 6 pierwszych wyrazów. Następnie to samo dla tablicy 128x7, 256x8 itd. Obliczając dla każdej tablicy iloraz parzystych do nieparzystych sami stwierdzicie, że ten iloraz rośnie do 2. I to jest klucz do problemu Collatza. Iloraz parzystych do nieparzystych we wszystkich ciągach Collatza wynosi 2. Tak więc nie może istnieć ciąg dążący do nieskończoności, bo naruszałoby to tę zasadę. Z omówionych tu dwóch czynników, decydujący jest ten o liczebności parzystych i to determinuje wszystkie ciągi do spadku do 1. Dziękuję, za przeczytanie.

Jak można zauważyć końcowy powtarzalny cykl zawsze zaczyna się od liczby \(\displaystyle{ 4}\). Oznacza to, że poprzednia liczba nie mogła być \(\displaystyle{ 1}\) (bo wtedy jesteśmy w cyklu). Zatem była to liczba \(\displaystyle{ 8}\). Czyli poprzednia musiała być liczba \(\displaystyle{ 16}\). Dalej są dwa warianty \(\displaystyle{ 5}\) i \(\displaystyle{ 32}\). Oznacza to że każdy ciąg musi przechodzić przez liczbę \(\displaystyle{ 16}\). Jeżeli chodzi o liczbę kroków do wejścia w cykl powtarzalny to może być ona dowolną. Czyli jeżeli mamy takie \(\displaystyle{ C_0}\) że liczba kroków do cyklu wynosi \(\displaystyle{ k}\) to by uzyskać \(\displaystyle{ C_1}\) o liczbie kroków \(\displaystyle{ n}\) większe od \(\displaystyle{ k}\) to wystarczy \(\displaystyle{ C_1=C_0 \cdot 2^{n-k} }\)

Prawdopodobny "dowód", że Collatz to geniusz trollingu.

Nie wiem, czy z regularności da się wyprowadzić jakieś wnioski w kontekście problemu Collatza, ale nieregularność na pewno ma wpływ na to, że tak trudno jest cokolwiek udowodnić.

Powyżej jest wizualizacja, dlaczego (moim zdaniem) nie można zapanować nad chaosem. Liczba 13 powinna być "węzłem" (wierzchołkiem grafu), w którym spotykają się 3 krawędzie, nie 2. Nie jest takim "węzłem", bo jest "troll" w postaci "czarnej" 4.

Czy więc chaos przesądza o niemożliwości dowiedzenia, że ciąg będzie malał do 4-2-1? Nie.

Moim zdaniem ciąg Collatza ma w sobie szkielet z ozdobnikami, które można pominąć. To jak z "h niemym" w różnych językach - np. "honour" w angielskim czytamy "onour" (upraszczam), "lehrerin" w niemieckim czytamy "lererin" (też upraszczam). Niby jest "h", ale tak naprawdę nie ma, bo nic nie znaczy, a jedynie utrudnia analizę statystyk liczby liter w języku mówionym i pisanym.

Z ciągiem Collatza jest tak samo. Spokojnie można go zredukować do postaci, w której będzie miał w sobie taką regularność:


Po redukcji liczby nieparzyste w nowym ciągu pozostaną te same co w oryginalnym i tak samo będą dążyć do 4-2-1.


Jak pozbyć się z ciągu Collatza niepotrzebnego "ozdobnika", tego "h niemego", który jedynie zakłóca analizę, a nic nie robi tak naprawdę?

Wystarczy podzielić przez 2, wykonując krok 3x+1.

Czyli:
gdy x jest parzysty, to x/2,
a
gdy x jest nieparzysty, to (3x+1)/2.

W ten sposób pomijamy "ozdobnik" (w przykładzie: 250 na czerwonym polu).

Jeśli ktoś uważa, że nie można się pozbyć "ozdobników", tylko że koniecznie trzeba pracować na oryginalnym ciągu Collatza, to niech po prostu traktuje liczbę nieparzystą i następującą po niej liczbę parzystą jako całość. Wtedy graf zawierający 3x+1 będzie wyglądał identycznie jak graf zawierający (3x+1)/2.

Już nie mam opcji edycji postu, a w pośpiechu zamieściłem złą grafikę.

"Po redukcji liczby nieparzyste w nowym ciągu pozostaną te same co w oryginalnym i tak samo będą dążyć do 4-2-1."
Liczby na czerwonych polach to "ozdobniki", które nic nie wnoszą.

Wiadomo, że dla x nieparzystego 3x+1 da liczbę parzystą, którą w następnym kroku należy podzielić przez 2. Można po prostu nie pisać tej liczby, bo ona na nic innego nie wpływa w samym ciągu (zwłaszcza na zbieżność do 4-2-1), natomiast utrudnia analizę.

Mój dowód, że wszystkie liczby nieparzyste (a więc także ich parzyste wielokrotności) znajdują się w grafie Collatza. A więc wszystkie liczby są zbieżne do 4-2-1.

Nie umiem tego rozpisać na wzory. Możliwe, że dla liczb nieparzystych to będzie coś w stylu
\(\displaystyle{ y = \left( x * 2^{n} * 2 - 1 \right) / 3 }\)

W sumie wrzucę "gałązkę" grafu (3x-1)/2.

Mechanika grafu jest identyczna dla 3x-1, o ile założymy, że "ozdobnik" będzie tworzył "podgrupę" z liczbą nieparzystą.

Czyli np. graf 1-2-4-8-(16-5)-10-20-40 będzie wyglądał identycznie jak graf 1-2-4-8-5-10-20-40.

Mam wrażenie, ze dla mechaniki grafu nie ma znaczenia na przykład, czy w danym miejscu jest kwadrat piątki 25 czy liczba pierwsza 79 - ważne, że żadna z tych liczb nie jest podzielna przez 2 lub 4.

Trochę żałuję, że nie mam narzędzi do tworzenia grafów. Ciekawe, jak wygląda profesjonalna wizualizacja grafu (3x-1)/2.

Słowo honoru, nie chciało mi się, bo temat zaczyna mnie nudzić

W ten sposób według mnie powinien wyglądać graf dla liczby 49 w ciągu Collatza:

Sednem w problemie Collatza jest to, że jeśli znamy rozkład pewnej liczby na czynniki pierwsze i dodamy do niej jedynkę, to już totalnie i nieprzewidywalnie zmienia się jej rozkład na czynniki pierwsze

https://ksetlak.pl/wp/my-collatz-conjecture-graph/

Mechanika binarna mojego grafu Collatza