Ludwiczek69 Ludwiczek69
0
BLOG

Problem Collatza. Część 5, czyli to co nie widać

Ludwiczek69 Ludwiczek69 Nauka Obserwuj temat Obserwuj notkę 0
matematyka

ollatza.A gdyby zmienić regułę Collatza? O rodzinie algorytmów, które tworzą własne cykle


1. Prosta zagadka, która nie chce dać się rozwiązać


Wyobraźmy sobie prostą zabawę z liczbami.


Wybieramy dowolną dodatnią liczbę całkowitą. Jeżeli jest parzysta, dzielimy ją przez dwa. Jeżeli jest nieparzysta, mnożymy ją przez trzy i dodajemy jeden.


Następnie powtarzamy tę samą procedurę z otrzymanym wynikiem.


To właśnie klasyczny algorytm Collatza, znany również jako problem 3n + 1.


Przykładowo, zaczynając od liczby 7, otrzymujemy ciąg:


7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.


Po osiągnięciu liczby 1 algorytm zaczyna powtarzać ten sam cykl:


1 -> 4 -> 2 -> 1.


Zasady są banalnie proste. Problem polega na tym, że do dziś nie udało się matematycznie udowodnić, iż każda dodatnia liczba całkowita, niezależnie od tego, od której zaczniemy, ostatecznie dotrze do tego cyklu.


To jeden z najbardziej znanych nierozwiązanych problemów teorii liczb.


Ale można zadać inne pytanie.


Czy zachowanie algorytmu jest związane z samymi zasadami dzielenia liczb parzystych i przekształcania nieparzystych, czy może decydują o nim konkretne wartości występujące w regule 3n + 1?


Spróbujmy to sprawdzić.


2. Co się stanie, jeśli zmienimy jedną regułę?


W klasycznym algorytmie mamy dwie operacje:


liczby parzyste dzielimy przez dwa;


liczby nieparzyste mnożymy przez trzy i dodajemy jeden.


Zachowajmy pierwszą operację bez zmian, ale drugą zastąpmy bardziej ogólną regułą:


Liczbę nieparzystą mnożymy przez a i dodajemy b.


Otrzymujemy rodzinę algorytmów:


dla liczby parzystej: dzielimy przez dwa;


dla liczby nieparzystej: obliczamy a*n+b.


Parametry a i b są liczbami całkowitymi. Przyjmujemy, że a jest dodatnie, a b nieujemne.


Klasyczny Collatz to po prostu szczególny przypadek tej rodziny, w którym a=3 i b=1.


Nie zmieniamy więc całej konstrukcji. Zmieniamy tylko jeden fragment reguły.


Można potraktować to jako eksperyment: sprawdzamy, czy niewielka zmiana parametrów wystarczy, aby algorytm zaczął tworzyć inne cykle.


3. Najpierw sprawdźmy parzystość


Zanim przejdziemy do przykładów, warto zauważyć coś prostego, ale istotnego.


Jeżeli liczba n jest nieparzysta, to parzystość wyniku a*n+b zależy wyłącznie od parzystości parametrów a i b.


Możliwe są cztery przypadki:


Jeżeli a i b są nieparzyste, wynik jest parzysty.


Jeżeli a jest nieparzyste, a b parzyste, wynik jest nieparzysty.


Jeżeli a jest parzyste, a b nieparzyste, wynik jest nieparzysty.


Jeżeli a i b są parzyste, wynik jest parzysty.


Dlaczego?


Liczba nieparzysta pomnożona przez liczbę nieparzystą daje wynik nieparzysty. Pomnożona przez liczbę parzystą daje wynik parzysty. Dodanie kolejnej liczby może zmienić parzystość wyniku.


W praktyce oznacza to, że dobierając parametry, możemy wpływać na to, czy po wykonaniu reguły nieparzystej algorytm od razu przejdzie do dzielenia przez dwa, czy ponownie zastosuje regułę dla liczby nieparzystej.


To niewielka zmiana, ale może mieć znaczenie dla całego ciągu.


4. Pierwszy eksperyment: zamiast 3n+1 zastosujmy 3n+5


Przyjmijmy teraz:


liczby parzyste dzielimy przez dwa;


liczby nieparzyste mnożymy przez trzy i dodajemy pięć.


Otrzymujemy algorytm T(3,5).


Co ciekawe, okazuje się, że ten sam algorytm może tworzyć różne cykle.


Cykl pierwszy


Zacznijmy od liczby 1.


Ponieważ jest nieparzysta, wykonujemy działanie:


3*1+5=8.


Następnie dzielimy przez dwa:


8 -> 4 -> 2 -> 1.


Otrzymujemy zamknięty cykl:


1 -> 8 -> 4 -> 2 -> 1.


Występują w nim cztery różne liczby.


Cykl drugi


Tym razem zacznijmy od liczby 5.


3*5+5=20.


Następnie:


20 -> 10 -> 5.


Otrzymujemy kolejny cykl:


5 -> 20 -> 10 -> 5.


Tym razem są to trzy różne liczby.


Cykl trzeci


Sprawdźmy jeszcze liczbę 19.


19 -> 62 -> 31 -> 98 -> 49 -> 152 -> 76 -> 38 -> 19.


Otrzymujemy trzeci cykl:


19 -> 62 -> 31 -> 98 -> 49 -> 152 -> 76 -> 38 -> 19.


Tym razem mamy osiem różnych liczb.


Wszystkie trzy cykle należą do tego samego algorytmu.


Nie są to trzy różne algorytmy. To trzy różne cykle jednej i tej samej reguły.


Warto jednak zachować ostrożność: znalezienie tych cykli nie oznacza, że znamy wszystkie cykle algorytmu T(3,5). Nie dowodzi również, że każda liczba początkowa musi do któregoś z nich dotrzeć.


Mamy natomiast konkretny przykład pokazujący, że zmiana jednego parametru może prowadzić do powstania kilku różnych struktur cyklicznych.


5. Czy możemy uzyskać cykle dowolnie długie?


Teraz dochodzimy do najciekawszej części konstrukcji.


Zamiast wybierać parametry przypadkowo, spróbujmy dobrać je w taki sposób, aby z góry wiedzieć, jaki cykl otrzymamy.


Pozostawmy mnożenie przez trzy, ale zmieńmy parametr dodawany do liczby nieparzystej.


Przyjmijmy:


a=3, b=2^k-3,


gdzie k jest dowolną liczbą całkowitą większą lub równą 2.


Co nam to daje?


Weźmy najpierw k=2.


Wtedy:


b=2^2-3=1.


Otrzymujemy klasyczny algorytm Collatza i cykl:


1 -> 4 -> 2 -> 1.


Teraz zwiększmy k do 3.


Wtedy:


b=2^3-3=5.


Otrzymujemy:


1 -> 8 -> 4 -> 2 -> 1.


Dla k=4:


b=2^4-3=13.


Cykl wygląda następująco:


1 -> 16 -> 8 -> 4 -> 2 -> 1.


Dla k=5:


b=2^5-3=29.


Otrzymujemy:


1 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.


Widzimy wyraźną prawidłowość.


Każde zwiększenie k o jeden powoduje zwiększenie długości cyklu o jeden element.


Czy jest to tylko przypadkowa zależność zauważona w kilku przykładach?


Nie. Możemy ją udowodnić.


6. Dlaczego ta konstrukcja zawsze działa?


Zacznijmy od liczby 1.


Dla każdego wybranego k nasz algorytm mnoży liczbę nieparzystą przez trzy i dodaje 2^k-3.


Otrzymujemy:


3*1+2^k-3=2^k.


Pierwszy krok zawsze prowadzi więc do potęgi dwójki.


A co dzieje się z potęgą dwójki?


Każda jest parzysta, dlatego algorytm dzieli ją przez dwa.


Otrzymujemy kolejno:


2^k -> 2^(k-1) -> 2^(k-2) -> ... -> 4 -> 2 -> 1.


Po powrocie do liczby 1 ponownie wykonujemy pierwszą regułę i otrzymujemy 2^k.


Cykl zostaje zamknięty.


Ważne jest również to, że wszystkie potęgi dwójki występujące w tym ciągu są różne. Żadna z nich nie jest równa 1, ponieważ rozpatrujemy potęgi od 2^1 do 2^k.


W cyklu mamy zatem:


jedną liczbę nieparzystą: 1;


dokładnie k różnych potęg dwójki.


Łącznie otrzymujemy k+1 różnych elementów.


Ponieważ k może być dowolnie dużą liczbą całkowitą, możemy konstruować algorytmy zawierające cykle o dowolnie dużej długości.


To nie jest już tylko obserwacja z kilku przykładów. Jest to wynik matematyczny, który wynika bezpośrednio z konstrukcji parametrów.


7. Co właściwie udało nam się wykazać?


Wynik jest dość prosty, ale warto dokładnie określić jego znaczenie.


Pokazaliśmy, że można zbudować nieskończenie wiele różnych algorytmów, które zachowują podstawową konstrukcję Collatza, ale mają inne parametry i cykle.


Co więcej, potrafimy z góry określić długość jednego z cykli w każdym z tych algorytmów.


Nie oznacza to jednak, że rozwiązaliśmy problem Collatza.


Nie wiemy jeszcze:


czy dla dowolnych parametrów a i b musi istnieć jakiś cykl;


ile cykli może zawierać jeden algorytm;


czy niektóre ciągi mogą rosnąć bez ograniczeń;


czy istnieje ogólna reguła pozwalająca przewidzieć długość cyklu;


jak zmienia się zachowanie algorytmu, gdy jednocześnie zmieniamy oba parametry.


Nie wiemy również, czy przedstawione przykłady dla T(3,5) wyczerpują wszystkie możliwe cykle tego algorytmu.


To ważne rozróżnienie. Udowodnienie istnienia konkretnego cyklu nie jest tym samym co udowodnienie, że wszystkie możliwe ciągi muszą do niego dotrzeć.


8. Co może być następnym krokiem?


Przedstawiona rodzina algorytmów daje możliwość dalszego badania zależności pomiędzy parametrami a powstającymi cyklami.


Do tej pory pokazaliśmy dwie rzeczy.


Po pierwsze, zmiana parametru b może doprowadzić do powstania kilku różnych cykli w obrębie jednego algorytmu.


Po drugie, istnieje prosta konstrukcja pozwalająca uzyskać algorytmy z cyklami o dowolnie dużej liczbie różnych elementów.


Kolejnym krokiem może być poszukiwanie bardziej ogólnych warunków, które określają, jakie cykle powstają dla różnych wartości a i b.


Być może pozwoli to lepiej zrozumieć, które właściwości wynikają z samego schematu algorytmu, a które są konsekwencją konkretnego doboru parametrów.


Na obecnym etapie mamy jednak przede wszystkim poprawną konstrukcję matematyczną i kilka konkretnych wyników. Dalsze uogólnienia wymagają osobnych dowodów.


Podsumowanie


Klasyczny problem Collatza opiera się na dwóch prostych regułach, ale jego globalne zachowanie pozostaje nierozstrzygnięte.


Zmieniając regułę dla liczb nieparzystych z 3n+1 na a*n+b, otrzymujemy całą rodzinę algorytmów zachowujących podstawowy schemat działania.


W jednym z nich, T(3,5), znaleźliśmy trzy różne cykle o długościach 3, 4 i 8 różnych elementów.


Następnie skonstruowaliśmy nieskończoną rodzinę algorytmów, w których można uzyskać cykle o dowolnie dużej długości.


Najważniejszy wniosek jest następujący:


Zachowując podstawowy schemat algorytmu Collatza, ale zmieniając jego parametry, możemy systematycznie generować różne struktury cykliczne.


To dopiero początek badania tej rodziny algorytmów, a nie rozwiązanie klasycznego problemu Collatza.



ps: może być to trudne do zrozumienia, ale działa to tak jak przejść z x+2, an x^2+2 (oczywiscie nie jest to to samo). Weryfikowalem to w kilku miejscach i poza błędami pismieniiczymi nie było zastrzezen. Jednak trzeba uwzględnić fakt że spory udział w tym miało AI, bo moj aparat matematyczny nie jest wystarczajacy

Ludwiczek69
O mnie Ludwiczek69

Nowości od blogera

Komentarze

Pokaż komentarze

Inne tematy w dziale Technologie