Archiwum

Posts Tagged ‘Dowód Hipotezy Collatza’

Pętle w ciągach typu collatza

21 kwietnia, 2012 4 Komentarze

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} =

2^{y-1} \cdot 2^{x^{'}} + 2^{y-2} \cdot p^{1} \cdot 2^{x^{''}} + 2^{y-3} \cdot p^{2} \cdot 2^{x^{'''}} + ... + 2^{1} \cdot p^{y-2} \cdot 2^{x^{y-1}}  + p^{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 \choose y} \cdot \frac {y} {y+x}= \frac {(4+4)!}{4! \cdot (4+4-4)!} \cdot \frac {4} {4+4}= 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!

————————————————————————–

PS Kilka osób zwracało się do mnie z prośbą o podanie dowodów przedstawionych tu wzorów. Zapodziałem gdzieś moje własne dowody, ale analogiczne wzory dla ciągu Collatza zdefiniowanego jako „3x+1” można znaleźć w niniejszym wpisie prof. Terence Tao:

https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/#expbound

Wyniki te można łatwo przekształcić na przypadek dowolnych ciągów postaci px+q.

Niedawno przypomniał mi się mój pierwotny dowód:

Rozważmy dowolną funkcję daną wzorem:

f(n) = \begin{cases} p \cdot n+ \frac {q} {2} \ \ \ gdy \ n \ jest \ nieparzyste\\ \ \ \frac {n}{2} \ \ \ \ \ \ \ \ \ \ \ \ gdy \ n \ jest \ parzyste\end{cases}

Zastąpmy wszystkie dzielenia przez liczbę 2 dzieleniem przez 2^{x_{i}} , przy czym 2^{x_{i}} może być dowolną liczbą naturalną lub zerem:

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

Policzmy kolejne y iteracji naszej nowej funkcji dla jakiejś liczby n :

f(f(...f(n)...)) = \frac {(\frac {p} {2})^{y}} {2^{x^{'}+...+x^{y}}} \cdot n + \frac {(\frac {p} {2})^{y-1} \cdot \frac {q} {2}} {2^{x^{'}+...+x^{y}}} + \frac {(\frac {p} {2})^{y-2} \cdot \frac {q} {2}} {2^{x^{''}+...+x^{y}}} + ... + \frac {\frac {q} {2}} {2^{x^{y}}}

Jeżeli w naszym ciągu występuje pętla, to:

n = f(f(...f(n)...))

n = \frac {(\frac {p} {2})^{y}} {2^{x^{'}+...+x^{y}}} \cdot n + \frac {(\frac {p} {2})^{y-1} \cdot \frac {q} {2}} {2^{x^{'}+...+x_{y}}} + \frac {(\frac {p} {2})^{y-2} \cdot \frac {q} {2}} {2^{x^{''}+...+x^{y}}} + ... + \frac {\frac {q} {2}} {2^{x^{y}}}

Pomnóżmy obie strony razy 2^{x^{'}+...+x^{y}} oraz podzielmy przez q . Niech x^{'}+...+x^{y} = x . Otrzymujemy:

\frac {2^{x+y} - p^{y}} {q} \cdot n = (\frac {p} {2})^{y-1} + (\frac {p} {2})^{y-2} \cdot 2^{x^{'}} + ... + 2^{x^{'}+...+2^{y-1}} \cdot 2^{y-1}

Liczba n zapętla się, zatem po y+x operacjach, gdy zachodzi:

n \cdot \frac {1} {q} = \frac {(\frac {p} {2})^{y-1} + (\frac {p} {2})^{y-2} \cdot 2^{x^{'}} + ... + 2^{x^{'}+...+2^{x^{y-1}}} \cdot 2^{y-1}} {2^{x+y} - p^{y}}

Nasz warunek można zapisać także jako (poniżej oznaczenia indeksów x^{i} zostały zamienione):

n \cdot \frac {1} {q} = [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} \cdot \frac {1} {2^{x+y} - p^{y}}

Jeżeli q = 2^{x+y} - p^{y} , mamy:

n = [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}

Liczbę q = 2^{x+y} - p^{y} można pomnożyć lub podzielić przez dwolną liczbę rzeczywistą r , wówczas, otrzymamy pętlę:

n \cdot r = [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}

Łatwo zauważyć, że:

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

oraz, że otrzymamy nieparzyste rozwiązania, tylko gdy:

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

 

Kategorie:Ciąg collatza, Ciągi typu - collatza, Hipoteza Collatza, Problem Collatza Tagi: , , , , , , , , , , , ,

Dowód Hipotezy Collatza?

15 kwietnia, 2012 2 Komentarze

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ć.

Kategorie:Ciąg collatza, Newsy Tagi: , , , , , , , , , , , , , , ,