Archiwum

Posts Tagged ‘Katy Perry’

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.

%d blogerów lubi to: