Archiwum

Posts Tagged ‘latex’

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: , , , , , , , , , , , ,