Serdecznie zachęcam do lektury!

Pętle w ciągach typu collatza

Kwiecień 21, 2012 2 uwag

W niniejszym artykule przedstawię wzór według którego możemy wyznaczyć wszystkie liczby (z oczywistych powodów ograniczam się tu tylko do podania wzoru na liczby nieparzyste) które zapętlają się w dowolnym ciągu typu collatza, postaci:

f(n) = \begin{cases} \frac {p}{2} \cdot n+ \frac {2^{x+y}-p^{y}}{2} \cdot r \ \ \ gdy \ n \ jest \ nieparzyste\\ \ \ \frac {n}{2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ gdy \ n \ jest \ parzyste\end{cases}

Niestety wzór jest na tyle złożony, że rozwiązanie za jego pomocą np. problemu collatza nadal pozostaje poza zasięgiem matematyków. Przejdźmy do definicji:

Niech p będzie dowolną nieparzystą liczbą naturalną.

Niech c będzie jakąś liczbą nieparzystą, zdefiniowaną następująco:

c = [1, (\frac {p}{2})^{1}, (\frac {p}{2})^{2}, ... , (\frac {p}{2})^{y-1}] \cdot \begin{bmatrix} 2^{x^{'}}\\2^{x^{''}}\\.\\.\\.\\2^{x^{y-1}}\\1\end{bmatrix} \cdot 2^{y-1}

oraz spełnione są warunki:

1) x^{'}, x^{''}, ... , x^{y-1} \in [0, x]

2) x^{'} \ge x^{''} \ge ... \ge x^{y-1}

 
Niech x będzie dowolną liczbą naturalną oraz ilością operacji typu n \mapsto \frac {n}{2} w pętli liczby L = c \cdot r .
Niech y będzie dowolną liczbą naturalną oraz ilością operacji typu n \mapsto \frac {p}{2} \cdot n + \frac {2^{x+y}-p^{y}}{2} \cdot r w pętli liczby L= c \cdot r .

Niech r będzie pewną liczbą wymierną (może być ujemna) taką, że (2^{x+y}-p^{y}) \cdot r jest liczbą całkowitą oraz c \cdot r także jest liczbą całkowitą.

 
Za pomocą niniejszego wzoru, po przyjęciu odpowiednich zmiennych definiujących nasz ciąg możemy wyznaczyć dowolne liczby L = c \cdot r zapętlające się w ciągach typu collatza. Na razie ograniczam się do podania owego wzoru ad hoc, jego wyprowadzenie zamieszczę w późniejszym terminie.

 
Przykład:

W pierwszej kolejności dobieramy zmienną p , przyjmijmy p=3 . Następnie określmy y=4 i x=4 , łatwo przewidzieć, że nasza pętla będzie miała zatem długość x+y=8 . Załóżmy, że r=3 . Definicja ciągu w którym będzie się zapętlać nasza liczba będzie zatem następujaca:

f(n) = \begin{cases} 1,5 \cdot n+ 262,5 \ \ \ gdy \ n \ jest \ nieparzyste\\ \ \ \frac {n}{2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ gdy \ n \ jest \ parzyste\end{cases}

 
Wyznaczmy c . Zauważmy, że możliwości różnego dobrania zmiennej c tak, aby spełnione były warunki:

1) x^{'}, x^{''}, ... , x^{y-1} \in [0, x]

2) x^{'} \ge x^{''} \ge ... \ge x^{y-1}

jest:

{x+y-1 \choose y-1} = \frac {(4+4-1)!}{4! \cdot (4-1)!} = 35

I dla każdej z tych możliwości dostaniemy pewną pętlę. My weźmiemy zmienną c określoną następująco:

c = [1, (\frac {3}{2})^{1}, (\frac {3}{2})^{2}, (\frac {3}{2})^{3}] \cdot \begin{bmatrix} 2^{3}\\2^{2}\\2^{2}\\1\end{bmatrix} \cdot 2^{3} = (8 + 6 + 9 + 3,375) \cdot 8 = 211

Liczba L która się zapętla w naszym ciągu wynosi zatem:

L=211 \cdot 3 = 633

A oto owa pętla:

633, 1212, 606, 303, 717, 1338, 669, 1266, 633, ...

Zachęcam do dalszego testowania wzoru i odkrywania nowych, nieodgadnionych meandrów ciągów typu collatza!

Dowód Hipotezy Collatza?

Kwiecień 15, 2012 2 uwag

Oto niedawna (mająca zaledwie 10 dni) propozycja dowodu z 5 kwietnia tego roku której autorem jest niejaki Peter Schorer z Hewlett-Packard:

A Solution to the 3x + 1 Problem

Publikacja liczy sobie niemal 60 stron, a autor przedstawia w niej – jak sam twierdzi kilka różnych dowodów Hipotezy Collatza. W jednym z początkowych akapitów podsumowuje strategię leżącą u podstaw wszystkich trzech dowodów w następujący sposób:

Informally, the strategy underlying all three proofs can be summarized by the following analogy: if we are searching for a needle in a haystack, and our researches reveal that more and more of the properties of the needle are the same as those of hay, then perhaps there is no needle in the haystack.

Nieformalnie strategię leżącą u podstaw wszystkich trzech dowodów można podsumować poprzez następująca analogię: jeśli szukamy igły w stogu siana, a nasze badania pokazują, że coraz więcej z właściwości igły jest takich samych jak siano, to być może w stogu siana wcale nie ma igły.

Nie przeczytałem co prawda całej publikacji, jednakowoż dowody które autor prezentuje robią wrażenie bardzo lakonicznych i nie wiadomo, czy nie wzbudzą zastrzeżeń i wątpliwości. Osobiście nie wierzę, że tak trudną hipotezę uda się udowodnić w tak minimalistyczny, wręcz elementarny sposób.

Zatem czy dowód jest fałszywy?

To zweryfikuje środowisko naukowe, tak jak w przypadku każdych publikacji czy dowodów. Niekiedy takie zaakceptowanie dowodu w środowisku naukowym trwa nawet kilka lat, a niekiedy ktoś znajduje błąd już po kilku tygodniach i publikacja zostaje wycofana. Pozostaje nam zatem cierpliwie czekać.

Problem Collatza – wprowadzenie

Kwiecień 9, 2012 1 komentarz

Problem Collatza problem postawiony po raz pierwszy w 1937 r. przez niemieckiego matematyka Lothara Collatza, znany również jako problem Ulama (po Stanisławie Ulamie), problem Kakutaniego (po Shizuo Kakutanim), problem Thwaites’ego (po Sir Bryanie Thwaitesie), algorytm Hassa (po Helmutcie Hassie), problem Syracuse, problem liczb Hailstone, problem liczb wondrous, problem „3x+1″, o wyjątkowo prostym – jak na złożoność problemu – sformułowaniu:

Definicja (Hipoteza Collatza):

- weźmy dowolną liczbę naturalną; następnie, jeżeli jest ona nieparzysta, pomnóżmy ją przez 3 oraz dodajmy do wyniku 1, natomiast jeżeli jest ona parzysta podzielmy ją przez 2; powtórzmy ten algorytm nieokreśloną ilość razy; hipoteza Collatza stwierdza, że niezależnie od jakiej liczby naturalnej zaczniemy, zawsze po pewnej skończonej ilości kroków otrzymamy liczbę 1.

W wyniku postępowania zgodnie z powyższym algorytmem otrzymamy ciąg liczb naturalnych, zwany ciągiem Collatza, który możemy określić rekurencyjnie poprzez funkcję f: \mathbb{N} \rightarrow \mathbb{N} :

f(x) = \begin{cases} 3x+1 \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ \ \ \ gdy \ x \ parzyste \end{cases}

lub ciąg zadany wzorem:

c_{n+1}=\frac {1}{2}c_{n} - \frac{1}{4}(5c_{n}+2)((-1)^{c_{n}}-1)

Powyższe definicje mają jednak dzisiaj jedynie znaczenie historyczne, ponieważ powszechnie spotykaną w literaturze oraz stosowaną w rozważaniach definicją ciągu collatza jest funkcja f: \mathbb{N} \rightarrow \mathbb{N} :

f(x) = \begin{cases} 1,5x+0,5 \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ gdy \ x \ parzyste \end{cases}

Zauważmy, że zadaje ona równoważny ciąg do oryginalnego ciągu collatza, pomijając niektóre parzyste wyrazy będące postaci 3x+1 , które zawsze dają się skrócić przez liczbę 2 , a ich pominięcie nie zmienia istoty samego problemu. Jako pierwszy ową skróconą formułę zaproponował Terras (1976, 1979).

Słaba i Silna Hipoteza Collatza:

Ze względu na nasuwającą się już od samego początku dychotomiczność problemu, Hipotezę Collatza podzielono na dwie pomniejsze hipotezy.

Silna Hipoteza Collatza stwierdza, że ciąg collatza jest zbieżny dla każdej liczby naturalnej inicjującej ciąg (i tym samym wpada w jakąś pętlę, niekoniecznie trywialną).

Słaba Hipoteza Collatza stwierdza, że jedyną pętlą występującą w ciągu colatza jest pętla trywialna (1,2,1,2,…).

Zauważmy, że hipotezy te nie wykluczają się.

Przykłady:

- zaczynając od x=5 otrzymamy ciąg:

5, 8, 4, 2, 1.

- zaczynając od x=9 otrzymamy ciąg:

9, 14, 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1.

- zaczynając od x=27 otrzymamy ciąg:

27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1.

Nie znaleziono jak dotąd wzoru pozwalającego obliczyć czas stopu (to znaczy ilość iteracji które trzeba wykonać, aby ciąg osiągnął jedynkę) dla dowolnej liczby w ciągu collatza. Ponadto wydaje się, iż jeżeli taki wzór istnieje to musi być niezwykle złożony ze względu na dużą nieregularność długości ciągu w stosunku do wielkości implementowanej liczby. Liczne publikacje oparte na teoretycznych przesłankach zweryfikowanych empirycznie wskazują jednak na silne korelacje długości ciągu oraz następującego wzoru:

d(n) \approx \frac {2}{ln(\frac {4}{3})} \cdot ln(n)

Przy czym d(n) to przewidywana długość ciągu dla liczby n .

Uogólnienie ciągu collatza na liczby całkowite ujemne:

Ciąg collatza można określić także dla liczb całkowitych ujemnych. Jak dotąd dla liczb całkowitych ujemnych wykryto trzy pętle:

- zaczynając od x=-1 otrzymamy ciąg:

-1, -1, -1, …

- zaczynając od x=-5 otrzymamy ciąg:

-5, -7, -10, -5, …

- zaczynając od x=-17 otrzymamy ciąg:

-17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34, -17, …

Można zauważyć, iż przekształcenia dla liczb ujemnych można równoważnie zdefiniować dla ciągu określonego na liczbach naturalnych za pomocą funkcji f: \mathbb{N} \rightarrow \mathbb{N} :

f(x) = \begin{cases} 1,5x-0,5 \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ gdy \ x \ parzyste \end{cases}

Próby rozwiązania hipotezy:

Istnieją dwie możliwości zaprzeczenia hipotezie:

a) dla jakiejś liczby ciąg wpada w cykl inny niż: 1,2,1,2,…
b) dla jakiejś liczby ciąg collatza jest rozbieżny do nieskończoności.

Przy czym możliwości te nie wykluczają się.

Wykazano prawdziwość hipotezy dla liczb mniejszych niż 20 \cdot 2^{58}\approx 5,764 \cdot 10^{18} .

Wiele osób uczestniczy w projekcie Collatz Conjecture którego celem jest rozwiazanie problemu poprzez znalezenie kontrprzykładu, a także obliczanie długości ciągów kolejnych coraz większych liczb i znajdowanie liczb-rekordzistów pod względem czasu stopu. Projekt Collatz Conjecture podlega platoformie BOINC (Otwartej Infrastrukturze Przetwarzania Rozproszonego Berkeley).

Z uwagi na złożoność problemu Paul Erdos wypowiedział o problemie słynne zdanie:

Mathematics is not yet ready for such problems.

(Matematyka nie jest jeszcze gotowa na takie problemy)

Jednakowoż kontrast pomiędzy prostotą sformułowania, a złożonością problemu wciąż przysparza matematykom wiele nowych prób często amatorskich i kompletnie błędnych dowodów.

Nagroda za rozwiązanie:

Paul Erdos zaoferował 500 dolarów za rozwiązanie hipotezy.

Thwaites (1996) zaoferował 1000 funtów nagrody za rozwiązanie hipotezy.

Follow

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.

%d bloggers like this: