Problem "5x+1" to modyfikacja znanego nierozwiązanego jak dotąd problemu collatza ("3x+1"). Rozważmy następujący ciąg:
Niech \(\displaystyle{ x}\) będzie dowolną liczbą naturalną.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} (5x+1)/2 \ gdy \ x \ nieparzyste\\x/2 \ \ \ \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
Problemy do rozstrzygnięcia:
(1) czy w ciągu występują jakieś liczby które się zapętlają? Jeśli tak, to czy jest ich skończenie czy nieskończenie wiele? Jakie są warunki ich występowania?
(2) ile liczb w ciągu wpada w pętle? (wpadanie liczby w pętlę to nie to samo co zapętlanie się liczby)
(3) czy ciąg ma jakieś rozbieżne trajektorie?
Już na pierwszy rzut oka można znaleźć w ciągu kilka przykładów pętli, na przykład dla liczb: 1, 33, 43. Natomiast na przykład liczba 19 wpada w pętlę liczby 1, a liczba 40 w pętlę liczby 43. Jakkolwiek większość ciągów bardzo szybko rośnie i wydaje się być rozbieżnych do nieskończoności (ale nie wiadomo czy faktycznie tak jest).
Moje pierwsze pytanie dotyczy tego czy na dziś dzień problem "5x+1" nadal pozostaje nierozwiązany, a w szczególności, czy nadal nie wiadomo czy ciąg ma jakieś rozbieżne trajektorie?
Jeffrey C. Lagarias w swojej pracy "The 3x + 1 Problem: An Overview" () pisze na temat "5x+1", że:
[...] stochastic models predict that almost all orbits should “escape to infinity”. These predictions are supported by experimental computer evidence, but it remains an unsolved problem to prove that there exists even one trajectory for the 5x + 1 problem that “escapes to infinity”.
[...] stochastyczne modele przewidują, że prawie wszystkie trajektorie powinny "uciekać do nieskończoności". Przewidywania te są wspierane przez komputerowe dowody eksperymentalne, ale pozostaje nierozwiązanym problemem udowodnić, że istnieje choćby jedna trajektoria dla problemu "5x + 1" która "ucieka do nieskończoności."
Pisząc o modelach stochastycznych ma tu zapewne na myśli metody spaceru losowego zastosowanego z dużym powodzeniem do problemu "3x+1" (przyjęto tam, że mnożenie z dodawaniem oraz dzielenie liczby w danym ciągu odbywa się z równym prawdpodobieństwem), a także losowego błądzenia iteracji wstecz. Te metody wydają się sugerować, że gęstość zbioru liczb nierozbieżnych do nieskończoności w ciągu wynosi 0, czyli, że prawie wszystkie są rozbieżne do nieskończonosci. Więcej szczegółów w tej publikacji: ... 1944v1.pdf. Jakkolwiek są to tylko eksperymentalne metody.
Ostatnia publikacja z arxiv.org jest z 2009 roku, zatem wydaje się, że problem raczej do dziś pozostaje nierozwiązany, natomiast nie wiem z którego roku jest ta pierwsza publikacja.
Moje drugie pytanie dotyczy tego, czy ktoś ma jakiś pomysł, aby udowodnić, że gęstość liczb nierozbieżnych do nieskończoności dla ciągu "5x+1" rzeczywiście jest zerowa? Ponieważ wydaje mi się, że Lagarias, ani nikt inny nie przedstawił nigdzie nie-eksperymentalnego dowodu. A wydawało mi się, że aktualna wiedza o problemie "3x+1" pozwala na rozstrzygnięcie tego problemu. W każdym razie myślę, że wiem jak można to zrobić.
Problem 5x+1
-
matemix
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Problem 5x+1
Pytałem o problem "5x+1", a nie o problem collatza. Czy Twoja odpowiedź dotyczy problemu "5x+1"?Timopumba pisze:Jeszcze 2 miesiące temu był nie rozwiązany, pewnie jest i nadal.
Ostatnio zmieniony 29 gru 2011, o 01:56 przez matemix, łącznie zmieniany 1 raz.
-
RSM
- Użytkownik
- Posty: 197
- Rejestracja: 1 lip 2011, o 21:41
- Płeć: Mężczyzna
- Lokalizacja: Internet
- Podziękował: 9 razy
- Pomógł: 13 razy
Problem 5x+1
Używasz chyba pojęć niestosowanych tradycyjnie, albo ja ich po prostu nie znam.
1. Co to są liczby, które się zapętlają?
2. Co to jest wpadanie liczby w pętlę?
3. Co to jest trajektoria, co to jest rozbieżna trajektoria?
4. Co to jest gęstość liczb? Wiem tylko co to gęstość zbioru.
5. Co to jest liczba rozbieżna/nierozbieżna do nieskończoności?
1. Co to są liczby, które się zapętlają?
2. Co to jest wpadanie liczby w pętlę?
3. Co to jest trajektoria, co to jest rozbieżna trajektoria?
4. Co to jest gęstość liczb? Wiem tylko co to gęstość zbioru.
5. Co to jest liczba rozbieżna/nierozbieżna do nieskończoności?
-
matemix
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Problem 5x+1
To możliwe. Wynika to z tego, że jest bardzo niewiele polsko-języcznych tekstów na ten temat, właściwie nie znam chyba żadnych polsko-języcznych książek, ani publikacji na ten temat, niektóre pojęcia znam prawdopodobnie ze skrótowych notek o problemie, a niektóre sam sformułowałem.
1. Liczba która się zapętla to taka liczba która generuje w ciągu po pewnej ilości iteracji dokładnie tą samą liczbę.
2. Wpadanie liczby w pętlę zachodzi, gdy dana liczba po pewnej ilości iteracji generuje inną liczbę która się zapętla.
3. Trajektoria ciągu dla danej liczby to po prostu ciąg jaki generuje ta liczba. Trajektoria rozbieżna, to przypadek ciągu liczb w którym pewne lub kolejne liczby ciągu rosną dla kolejnych wyrazów i nie ma ograniczenia dla tego wzrostu (rosną do nieskończoności).
4. Gęstość liczb - miałem oczywiście na myśli gęstość zbioru tych liczb w zbiorze liczb naturalnych.
5. Liczba rozbieżna do nieskończoności - liczba dla której trajektoria ciągu jest rozbieżna.
1. Liczba która się zapętla to taka liczba która generuje w ciągu po pewnej ilości iteracji dokładnie tą samą liczbę.
2. Wpadanie liczby w pętlę zachodzi, gdy dana liczba po pewnej ilości iteracji generuje inną liczbę która się zapętla.
3. Trajektoria ciągu dla danej liczby to po prostu ciąg jaki generuje ta liczba. Trajektoria rozbieżna, to przypadek ciągu liczb w którym pewne lub kolejne liczby ciągu rosną dla kolejnych wyrazów i nie ma ograniczenia dla tego wzrostu (rosną do nieskończoności).
4. Gęstość liczb - miałem oczywiście na myśli gęstość zbioru tych liczb w zbiorze liczb naturalnych.
5. Liczba rozbieżna do nieskończoności - liczba dla której trajektoria ciągu jest rozbieżna.
Ostatnio zmieniony 29 gru 2011, o 10:22 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Nie cytuj całego poprzedniego posta.
Powód: Nie cytuj całego poprzedniego posta.
-
Timopumba
- Użytkownik
- Posty: 31
- Rejestracja: 1 lut 2011, o 16:52
- Płeć: Mężczyzna
- Lokalizacja: okolice Lublina
- Podziękował: 3 razy
Problem 5x+1
matemix pisze:Pytałem o problem "5x+1", a nie o problem collatza. Czy Twoja odpowiedź dotyczy problemu "5x+1"?Timopumba pisze:Jeszcze 2 miesiące temu był nie rozwiązany, pewnie jest i nadal.
A to sorry chodziło mi o problem problem collatza
-
matemix
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Problem 5x+1
Moim zdaniem to, że prawie wszystkie liczby w ciągu "5x+1" są rozbieżne do nieskończoności można udowodnić w przedstawiony poniżej sposób.
Rozbieżność do nieskończoności ciągu "5x+1":
0. Definicja ciągu:
Niech \(\displaystyle{ x}\) będzie dowolną liczbą naturalną.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {5x+1}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
I. Opis ciągu za pomocą równań diofantycznych.
1. Każdy ciąg „5x+1” można opisać za pomocą następującego równania:
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}) \cdot \frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}=2^{w+x-v} \cdot ((2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v})}\)
Zmienne \(\displaystyle{ a_{j}, k_{j}, ... , x, p, q}\) należą do liczb naturalnych (bez zera), zmienne \(\displaystyle{ w}\) oraz \(\displaystyle{ v}\) należą do liczb naturalnych z zerem.
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) to liczba wejściowa od której zaczynamy ciąg (\(\displaystyle{ w}\) określa jej parzystość).
\(\displaystyle{ (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\) to liczba końcowa na której kończymy rozważany ciąg (\(\displaystyle{ v}\) określa jej parzystość).
Zmiennie \(\displaystyle{ a_{j}}\) określają ilość mnożeń z dodawaniem \(\displaystyle{ 2,5x+0,5}\) liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\), natomiast zmiennie \(\displaystyle{ k_{j}}\) określają tylko wielkość liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\). Zauważmy, że:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \underbrace {\cdot 2,5+0,5) \cdot 2,5+0,5\ldots}_{a \ razy} = 5^{a{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}\)
\(\displaystyle{ i = a_{1}+...+a_{n}+(w+x-v)}\) to ilość iteracji jakie wykonujemy w danym ciągu, aby obliczyć jego wyraz \(\displaystyle{ (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\).
Przykład:
\(\displaystyle{ 14, 7, 18, 9, 23, 58, 29}\)
\(\displaystyle{ ((2^{1} \cdot \frac {11}{3}-\frac {1}{3}) \cdot 2^{1}) \cdot \frac {5^{1} \cdot \frac {11}{3}-\frac {1}{3}}{2^{1} \cdot \frac {11}{3}-\frac {1}{3}} \cdot \frac {5^{2} \cdot \frac {7}{3}-\frac {1}{3}}{2^{2} \cdot \frac {7}{3}-\frac {1}{3}}=2^{1+2-0} \cdot ((2^{3} \cdot \frac {11}{3}-\frac {1}{3}) \cdot 2^{0})}\)
\(\displaystyle{ 14 \cdot \frac {18}{7} \cdot \frac {58}{9} = 8 \cdot 29}\)
2. Rozważmy pewien ciąg przekształceń jakiemu poddawana jest liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) w ciągu w wyniku którego otrzymujemy pewną liczbę \(\displaystyle{ (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\). Przekształcenia te można opisać następująco:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \cdot \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) + \frac{2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}}=(2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\)
Zdefiniujmy \(\displaystyle{ r\alpha(k)}\) jako współczynnik przez który mnożona jest liczba poddawana pewnej dowolnej sekwencji przekształceń:
\(\displaystyle{ r\alpha(k) = \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) + \frac{2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}} = \frac {(2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}{(2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}}\)
przy czym litera \(\displaystyle{ k}\) w nawiasie oznacza, iż istotna jest tu kolejność wykonywanych działań.
3. Zdefiniujmy współczynniki \(\displaystyle{ \alpha(k)}\) oraz \(\displaystyle{ \beta(k)}\) jako:
\(\displaystyle{ \alpha(k) = \frac {2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}}}\)
\(\displaystyle{ \beta(k) = \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) \cdot (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\)
Przy czym przyjmujemy, że \(\displaystyle{ \alpha_{1}(k) = \alpha_{2}(k)}\), tylko gdy zachowana jest kolejność wykonywanych przekształceń w ciągu, a nie gdy zachodzi arytmetyczna równość (jednak powyższy skrócony zapis nie niesie ze sobą konkretnej informacji o kolejności działań).
Zauważmy, iż zachodzi następująca równość:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \cdot r\alpha(k)}\)
II. Struktura przekształceń w ciągu.
Każde mnożenie wraz z dodawaniem: \(\displaystyle{ 2,5 \cdot x + 0,5}\) nazwiemy przyrostem ciągu. Każde dzielenie przez 2 nazwiemy spadkiem ciągu.
1. Dla danej długości iteracji \(\displaystyle{ i}\) ciąg może przyjmować \(\displaystyle{ 2^{i}}\) różnych wariacji z powtórzeniami przyrostów i spadków (teoretycznie, dowód w pkt. 3).
2. Wariacje te określają nam jednoznacznie zbiór \(\displaystyle{ i+1}\) różnych współczynników \(\displaystyle{ \alpha}\) które można obliczyć zgodnie z następującym wzorem:
\(\displaystyle{ (p+q)^{i} \cdot 3^{i} = \alpha_{1} + \alpha_{2} + \alpha_{3} + ... + \alpha_{i+1}}\)
\(\displaystyle{ p=\frac {1}{6}}\)
\(\displaystyle{ q=\frac {5}{6}}\)
3. Twierdzenie: każda z wariacji bez powtórzeń dla dowolnego zbioru \(\displaystyle{ 2^{i}}\) liczb następujących po sobie (dla danej długości iteracji \(\displaystyle{ i}\)) ma realizację w ciągu dla dokładnie jeden raz. Przekształcenia w ciągu mają zatem rozkład dwumianowy – w pewnym zakresie (w zakresie \(\displaystyle{ i}\) iteracji). Twierdzenie to orzeka innymi słowy: dla dowolnej ilości \(\displaystyle{ 2^{i}}\) liczb następujących po sobie dla danej długości iteracji \(\displaystyle{ i}\) ciąg przyjmuje \(\displaystyle{ 2^{i}}\) różnych wariacji z powtórzeniami przyrostów i spadków.
Dowód:
Załóżmy, że jakaś liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \in N}\) realizuje jedną z kombinacji przyrostów i spadków \(\displaystyle{ \alpha(k) = \frac {2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}}}\). Wówczas w oczywisty sposób możemy dla tej liczby jednoznacznie określić \(\displaystyle{ \beta(k) = \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) \cdot (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\).
Rozważmy teraz liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+1, (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2, ... , (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2^{i}-1}\).
Sprawdźmy, czy liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+1}\) poddana temu samemu przekształceniu co \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) może być liczbą całkowitą (przyjmujemy tu założenie które udowodnimy później, że dwie liczby poddawane temu samemu przekształceniu mają te same współczynniki \(\displaystyle{ \beta(k)}\)):
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+1) \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} + \frac {2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}} \not\in N}\)
. . .
. . .
. . .
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2^{i}-1) \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} + \frac {(2^{i}-1) \cdot 2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}} \not\in N}\)
Analogicznie warunku nie spełniają pozostałe liczby (spełnia go dopiero liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2^{i}}\)). Dowodzi to naszego twierdzenia, że każda z wariacji bez powtórzeń dla dowolnego zbioru \(\displaystyle{ 2^{i}}\) liczb następujących po sobie ma realizację w ciągu dokładnie jeden raz, ponieważ wiemy, że przekształcenia w ciągu "5x+1" nie mogą nas wyprowadzać poza zbiór liczb \(\displaystyle{ N}\).
4. Twierdzenie: dwie dowolne liczby poddawane w ciągu temu samemu przekształceniu (tj. wykonywane są na nich te same działania w tej samej kolejności) mają te same współczynniki \(\displaystyle{ \beta(k)}\).
Dowód:
Aby udowodnić słuszność tego twierdzenia wystarczy wykazać, iż współczynniki \(\displaystyle{ \beta(k)}\) zależą wyłącznie od tego w jakiej kolejności i jakie działania wykonujemy na liczbach (a nie od wielkości liczb). Weźmy dowolną liczbę naturalna \(\displaystyle{ g}\) oraz zdefiniujmy dla niej pewien dowolny ciąg przekształceń:
\(\displaystyle{ \left(\frac {\frac {g \cdot 2,5^{a_{1}}+\frac{5}{6} \cdot 2,5^{a_{1}-1}- \frac{1}{3}}{2^{x_{1}}} \cdot 2,5^{a_{2}}+\frac {5}{6} \cdot 2,5^{a_{2}-1}-\frac {1}{3}}{2^{x_{2}}} \cdot \ldots \cdot 2,5^{a_{n}}+\frac {5}{6} \cdot 2,5^{a_{n}-1}-\frac {1}{3}}\right)/2^{x_{n}} = g \cdot \frac {2,5^{a_{1}+...+a_{n}}}{2^{x_{1}+...+x_{n}}} + \frac {(\frac {5}{6} \cdot 2,5^{a_{1}-1}-\frac {1}{3}) \cdot 2,5^{a_{2}+...+a_{n}}}{2^{x_{1}+...+x_{n}}} + \frac {(\frac {5}{6} \cdot 2,5^{a_{2}-1}-\frac {1}{3}) \cdot 2,5^{a_{3}+...+a_{n}}}{2^{x_{2}+...+x_{n}}} + ... + \frac {(\frac {5}{6} \cdot 2,5^{a_{n}-1}-\frac {1}{3})}{2^{x_{n}}} \in N}\)
Zauważmy, że:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2,5^{a_{1}}+\frac {5}{6} \cdot 2,5^{a_{1}-1}- \frac {1}{3} = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \underbrace {\cdot 2,5+0,5) \cdot 2,5+0,5\ldots}_{a \ razy} = 5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}\)
Współczynnik \(\displaystyle{ \beta(k)}\) wynosi zatem:
\(\displaystyle{ \beta(k) = \frac {(\frac{5}{6} \cdot 2,5^{a_{1}-1}-\frac {1}{3}) \cdot 2,5^{a_{2}+...+a_{n}}}{2^{x_{1}+...+x_{n}}} + \frac{(\frac {5}{6} \cdot 2,5^{a_{2}-1}- \frac {1}{3}) \cdot 2,5^{a_{3}+...+a_{n}}}{2^{x_{2}+...+x_{n}}} + ... + \frac{(\frac {5}{6} \cdot 2,5^{a_{n}-1}-\frac {1}{3})}{2^{x_{n}}}}\)
Widać zatem, że \(\displaystyle{ \beta(k)}\) zależy wyłącznie od tego w jakiej kolejności, ile i jakie działania zostały wykonanie na liczbie \(\displaystyle{ g}\), natomiast jest niezależny od wielkości \(\displaystyle{ g}\) (ponieważ nie zależy od współczynników \(\displaystyle{ k_{j}}\) które odpowiadają za wielkość liczb).
Łatwo można zauważyć, iż liczb spełniających powyższe równania jest nieskończenie wiele i są one postaci:
\(\displaystyle{ g = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} + 2^{i} \cdot r}\) , \(\displaystyle{ r = 0, 1, 2, ...}\)
5. Twierdzenie: w ciągu "5x+1" przy danej długości ciągu i cyklicznie powtarzają się te same sekwencje przekształceń i następuje to co okres \(\displaystyle{ 2^{i}}\) liczb.
Dowód:
Dowodzi tego zapisany już powyżej wzór:
\(\displaystyle{ g = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} + 2^{i} \cdot r}\)
wynika z niego, że:
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} + 2^{i} \cdot r) \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} + 5^{a_{1}+...+a_{n}} \cdot r \in N}\)
Możemy z niego łatwo wyznaczyć także wartości \(\displaystyle{ i-tych}\) iteracji dla liczb przesuniętych od liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) o dowolną wielokrotność \(\displaystyle{ 2^{i}}\) (czyli o \(\displaystyle{ 2^{i} \cdot r}\)).
6. Twierdzenie: suma współczynników \(\displaystyle{ \alpha(k)}\) w poszczególnych wierszach na przedziałach \(\displaystyle{ 2^{i}}\) kolejnych liczb jest stała i wynosi \(\displaystyle{ 3^{i}}\).
Dowód: twierdzenie to wynika bezpośrednio ze wzoru II. 2. oraz z twierdzenia II. 3.
III. Rozbieżność do nieskończoności ciągu "5x+1".
1. Rozważmy różne (tj. nierówne arytmetycznie) współczynniki \(\displaystyle{ \alpha(k)}\) na przedziale liczb \(\displaystyle{ (1; 2^{i})}\) dla \(\displaystyle{ i-tej}\) iteracji. Zauważmy, iż jest ich \(\displaystyle{ i+1}\).
Twierdzenie: dla \(\displaystyle{ i}\) dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) ilość różnych współczynników \(\displaystyle{ \alpha(k)}\) większych od 1 wynosi \(\displaystyle{ (i+1) \cdot \frac {ln(2)}{ln(5)}}\).
Dowód:
Aby sobie to uświadomić weźmy skończony \(\displaystyle{ (i+1)}\) - wyrazowy ciąg którego kolejne wyrazy zmieniają się jak różne współczynniki \(\displaystyle{ \alpha(k)}\):
\(\displaystyle{ c_1=\frac {5^0}{2^i}}\)
\(\displaystyle{ c_2=\frac {5^1}{2^i}}\)
\(\displaystyle{ c_3=\frac {5^2}{2^i}}\)
\(\displaystyle{ c_4=\frac {5^3}{2^i}}\)
...
\(\displaystyle{ c_{(i+1)}=\frac {5^i}{2^i}}\)
W tym ciągu istnieje pewien wyraz graniczny \(\displaystyle{ c_{g}}\) poniżej którego wszystkie wyrazy są mniejsze od 1 i powyżej którego wszystkie są większe od 1 i który sam jest też większy od 1. Szukamy granicy:
\(\displaystyle{ \lim_{i+1\to\infty} \frac {i+1}{g}}\)
Przy czym \(\displaystyle{ g}\) to numer wyrazu granicznego. Mamy zatem ciąg:
\(\displaystyle{ c(i,k)=\frac{5^i}{2^k}}\)
gdzie \(\displaystyle{ k}\) to pewna stała, szukamy największego takiego \(\displaystyle{ i}\) że:
\(\displaystyle{ c(i,k)>1}\)
logarytmujemy sobie stronami:
\(\displaystyle{ \ln c(i,k)>0}\)
czyli:
\(\displaystyle{ \ln 5^i - \ln 2^k>0\\
i\ln 5 > k\ln 2 \\
i > k \frac{\ln 2}{\ln 5}}\)
Najmniejszym takim całkowitym \(\displaystyle{ i}\) jest oczywiście:
\(\displaystyle{ i_g=\left\lfloor k \frac{\ln 2}{\ln 5} \right\rfloor+1}\)
Teraz chcemy znaleźć granicę:
\(\displaystyle{ \lim_{k\to \infty} \frac{k+1}{i_g}=\lim_{k\to \infty} \frac{k+1}{\left\lfloor k \frac{\ln 2}{\ln 5} \right\rfloor+1}}\)
Szacujemy ją z 3 ciągów i dostajemy granicę:
\(\displaystyle{ \frac {ln(5)}{ln(2)}}\)
2. Rozważmy wszystkie współczynniki \(\displaystyle{ \alpha(k)}\) na przedziale liczb \(\displaystyle{ (1; 2^{i})}\) dla \(\displaystyle{ i-tej}\) iteracji. Zauważmy, iż jest ich \(\displaystyle{ 2^{i}}\).
Twierdzenie: dla \(\displaystyle{ i}\) dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) gęstość współczynników \(\displaystyle{ \alpha(k)}\) większych od 1 jest równa \(\displaystyle{ 2^{i}}\) (zachodzi tu asymptotyczna równość).
Dowód:
Zauważmy, że częstości występowania poszczególnych różnych \(\displaystyle{ i-tych}\) współczynników \(\displaystyle{ \alpha(k)}\) są zadane wartościami liczb w danym \(\displaystyle{ i-tym}\) wierszu trójkąta Pascala. Wobec tego należy obliczyć następującą granicę:
\(\displaystyle{ \lim_{i\to\infty} \frac {\sum_{k=0}^{[\frac {ln(2) \cdot i}{ln(5)}]} {i\choose k}}{2^{i}}=1}\)
Wyrażenie w mianowniku to suma wszystkich współczynników na przedziale \(\displaystyle{ (1; 2^{i})}\) dla \(\displaystyle{ i-tej}\) iteracji, natomiast wyrażenie w mianowniku określa ilość współczynników \(\displaystyle{ \alpha(k)}\) mniejszych od 1 (kolejne współczynniki trójkąta Pascala obliczane z dwumianu Newtona). Wynosi ona 1, zatem dla \(\displaystyle{ i}\) dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) gęstość współczynników \(\displaystyle{ \alpha(k)}\) mniejszych od 1 jest równa \(\displaystyle{ 2^{i}}\).
Dowód:
Szukamy dowodu twierdzenia, że dla rozkładu dwumianowego przy ilości prób \(\displaystyle{ n}\) dążącej do nieskończoności i \(\displaystyle{ p=0,5}\) suma jego wartości od wartości pierwszej do wartości \(\displaystyle{ n \cdot (0,5+y)}\) podzielona przez sumę wszystkich wartości (od 1 do \(\displaystyle{ n}\)) czyli przez \(\displaystyle{ 2^{n}}\) dąży do 1. Przy czym \(\displaystyle{ y}\) to dowolna stała większa od 0 i mniejsza od 0,5 (w naszym przypadku \(\displaystyle{ y}\) jest ujemne, ale to nie ma znaczenia ze względu na symetryczność rozkładu normalnego dla tak przyjętego prawdopodobieństwa).
Rozkład dwumianowy, gdy liczba prób \(\displaystyle{ n}\) dąży do nieskończoności jest zbieżny do rozkładu normalnego \(\displaystyle{ N\sim\left(np, \sqrt{np\left(1-p\right)\right)}}\). Można zatem zbadać ile wynosi ta granica dla rozkładu normalnego przy \(\displaystyle{ \mu=n \cdot 0,5}\) oraz \(\displaystyle{ \sigma=\sqrt{n \cdot 0,25}}\). Rozkład normalny dany jest wzorem:
\(\displaystyle{ f(\mu,\sigma,x) = \frac {1} {\sigma \cdot (2 \pi)^{0,5}} \cdot e^{\frac {-(x-\mu)^{2}}{2 \cdot (\sigma)^{2}}}}\)
A w naszym przypadku:
\(\displaystyle{ f\left(x, n\right) = \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}}}\)
Należy zatem obliczyć granicę:
\(\displaystyle{ \lim_{n\to\infty} \frac {\int\limits_{-\infty}^{(0,5+y) \cdot n} \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}} dx} {\int\limits_{-\infty}^{n} \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}} dx}}\)
I udowodnić, że wynosi ona \(\displaystyle{ 1}\), dla każdego \(\displaystyle{ 0<y<0,5}\).
Całka z \(\displaystyle{ f(x,n)}\) wynosi:
\(\displaystyle{ \int\limits_{-\infty}^{\left(0,5+y\right) \cdot n} \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}} \text{d}x = 0,5 \cdot \mathrm{erf} \left(\frac {\sqrt{2}} {2} \cdot \sqrt{n}\right) + 0,5 \cdot \mathrm{erf} \left(\sqrt{2} \cdot y \cdot \sqrt{n}\right) + 0,5 \cdot erfc\left(\frac {\sqrt{n}}{\sqrt{2}}\right)}\)
Druga całka wynosi oczywiście 1, zatem liczymy granicę:
przyjmujemy \(\displaystyle{ y=0,5-\frac {ln(2)}{ln(5)}}\)
\(\displaystyle{ \lim_{n\to\infty} \left(0,5 \cdot \mathrm{erf} \left(\frac {\sqrt{2}} {2} \cdot \sqrt{n}\right) + 0,5 \cdot \mathrm{erf} \left(\sqrt{2} \cdot y \cdot \sqrt{n}\right) + 0,5 \cdot erfc\left(\frac {\sqrt{n}}{\sqrt{2}}\right)\right)=1}\)
3. Twierdzenie: zbiór liczb nierozbieżnych do nieskończoności w ciągu „5x+1” ma gęstość 0.
Wynika z twierdzenia III. 2. Skoro dla i dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) gęstość współczynników \(\displaystyle{ \alpha(k)}\) większych od 1 jest równa \(\displaystyle{ 2^{i}}\) (oraz przyjmują one rozkład normalny), to zbiór liczb właśnie o gęstości \(\displaystyle{ 2^{i}}\) (przy \(\displaystyle{ i}\) dążącym do nieskończoności) jest rozbieżny do nieskończoności. Rozbieżność zachodzi już dla współczynników \(\displaystyle{ \alpha(k)}\). A skoro zachodzi dla \(\displaystyle{ \alpha(k)}\), to tym bardziej zachodzi dla \(\displaystyle{ r\alpha(k)}\), ponieważ \(\displaystyle{ r\alpha(k)>\alpha(k)}\).
Będę wdzięczny za wszelkie uwagi.
-- 3 stycznia 2012, 16:44 --
Gwoli ścisłości zgodnie z książką "The ultimate challenge: the 3x+1 problem" - Jeffrey'a C. Lagarias'a hipoteza, że każda liczba w ciągu "5x+1" zbiega do jedynki nosi nazwę hipotezy "5x+1" Kakutaniego.
-- 3 stycznia 2012, 17:01 --
Rozbieżność do nieskończoności ciągu "5x+1":
0. Definicja ciągu:
Niech \(\displaystyle{ x}\) będzie dowolną liczbą naturalną.
\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {5x+1}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}}\)
I. Opis ciągu za pomocą równań diofantycznych.
1. Każdy ciąg „5x+1” można opisać za pomocą następującego równania:
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}) \cdot \frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}=2^{w+x-v} \cdot ((2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v})}\)
Zmienne \(\displaystyle{ a_{j}, k_{j}, ... , x, p, q}\) należą do liczb naturalnych (bez zera), zmienne \(\displaystyle{ w}\) oraz \(\displaystyle{ v}\) należą do liczb naturalnych z zerem.
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) to liczba wejściowa od której zaczynamy ciąg (\(\displaystyle{ w}\) określa jej parzystość).
\(\displaystyle{ (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\) to liczba końcowa na której kończymy rozważany ciąg (\(\displaystyle{ v}\) określa jej parzystość).
Zmiennie \(\displaystyle{ a_{j}}\) określają ilość mnożeń z dodawaniem \(\displaystyle{ 2,5x+0,5}\) liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\), natomiast zmiennie \(\displaystyle{ k_{j}}\) określają tylko wielkość liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\). Zauważmy, że:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \underbrace {\cdot 2,5+0,5) \cdot 2,5+0,5\ldots}_{a \ razy} = 5^{a{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}\)
\(\displaystyle{ i = a_{1}+...+a_{n}+(w+x-v)}\) to ilość iteracji jakie wykonujemy w danym ciągu, aby obliczyć jego wyraz \(\displaystyle{ (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\).
Przykład:
\(\displaystyle{ 14, 7, 18, 9, 23, 58, 29}\)
\(\displaystyle{ ((2^{1} \cdot \frac {11}{3}-\frac {1}{3}) \cdot 2^{1}) \cdot \frac {5^{1} \cdot \frac {11}{3}-\frac {1}{3}}{2^{1} \cdot \frac {11}{3}-\frac {1}{3}} \cdot \frac {5^{2} \cdot \frac {7}{3}-\frac {1}{3}}{2^{2} \cdot \frac {7}{3}-\frac {1}{3}}=2^{1+2-0} \cdot ((2^{3} \cdot \frac {11}{3}-\frac {1}{3}) \cdot 2^{0})}\)
\(\displaystyle{ 14 \cdot \frac {18}{7} \cdot \frac {58}{9} = 8 \cdot 29}\)
2. Rozważmy pewien ciąg przekształceń jakiemu poddawana jest liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) w ciągu w wyniku którego otrzymujemy pewną liczbę \(\displaystyle{ (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\). Przekształcenia te można opisać następująco:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \cdot \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) + \frac{2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}}=(2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}\)
Zdefiniujmy \(\displaystyle{ r\alpha(k)}\) jako współczynnik przez który mnożona jest liczba poddawana pewnej dowolnej sekwencji przekształceń:
\(\displaystyle{ r\alpha(k) = \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) + \frac{2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}} = \frac {(2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v}}{(2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}}\)
przy czym litera \(\displaystyle{ k}\) w nawiasie oznacza, iż istotna jest tu kolejność wykonywanych działań.
3. Zdefiniujmy współczynniki \(\displaystyle{ \alpha(k)}\) oraz \(\displaystyle{ \beta(k)}\) jako:
\(\displaystyle{ \alpha(k) = \frac {2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}}}\)
\(\displaystyle{ \beta(k) = \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) \cdot (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\)
Przy czym przyjmujemy, że \(\displaystyle{ \alpha_{1}(k) = \alpha_{2}(k)}\), tylko gdy zachowana jest kolejność wykonywanych przekształceń w ciągu, a nie gdy zachodzi arytmetyczna równość (jednak powyższy skrócony zapis nie niesie ze sobą konkretnej informacji o kolejności działań).
Zauważmy, iż zachodzi następująca równość:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \cdot r\alpha(k)}\)
II. Struktura przekształceń w ciągu.
Każde mnożenie wraz z dodawaniem: \(\displaystyle{ 2,5 \cdot x + 0,5}\) nazwiemy przyrostem ciągu. Każde dzielenie przez 2 nazwiemy spadkiem ciągu.
1. Dla danej długości iteracji \(\displaystyle{ i}\) ciąg może przyjmować \(\displaystyle{ 2^{i}}\) różnych wariacji z powtórzeniami przyrostów i spadków (teoretycznie, dowód w pkt. 3).
2. Wariacje te określają nam jednoznacznie zbiór \(\displaystyle{ i+1}\) różnych współczynników \(\displaystyle{ \alpha}\) które można obliczyć zgodnie z następującym wzorem:
\(\displaystyle{ (p+q)^{i} \cdot 3^{i} = \alpha_{1} + \alpha_{2} + \alpha_{3} + ... + \alpha_{i+1}}\)
\(\displaystyle{ p=\frac {1}{6}}\)
\(\displaystyle{ q=\frac {5}{6}}\)
3. Twierdzenie: każda z wariacji bez powtórzeń dla dowolnego zbioru \(\displaystyle{ 2^{i}}\) liczb następujących po sobie (dla danej długości iteracji \(\displaystyle{ i}\)) ma realizację w ciągu dla dokładnie jeden raz. Przekształcenia w ciągu mają zatem rozkład dwumianowy – w pewnym zakresie (w zakresie \(\displaystyle{ i}\) iteracji). Twierdzenie to orzeka innymi słowy: dla dowolnej ilości \(\displaystyle{ 2^{i}}\) liczb następujących po sobie dla danej długości iteracji \(\displaystyle{ i}\) ciąg przyjmuje \(\displaystyle{ 2^{i}}\) różnych wariacji z powtórzeniami przyrostów i spadków.
Dowód:
Załóżmy, że jakaś liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} \in N}\) realizuje jedną z kombinacji przyrostów i spadków \(\displaystyle{ \alpha(k) = \frac {2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}}}\). Wówczas w oczywisty sposób możemy dla tej liczby jednoznacznie określić \(\displaystyle{ \beta(k) = \frac {1}{2^{w+x-v}} \cdot (\frac {5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}{2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}} \cdot ... \cdot \frac {5^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}}{2^{a_{n}} \cdot \frac {k_{n}}{3}-\frac {1}{3}} – 2,5^{a_{1}+...+a_{n}}) \cdot (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\).
Rozważmy teraz liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+1, (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2, ... , (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2^{i}-1}\).
Sprawdźmy, czy liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+1}\) poddana temu samemu przekształceniu co \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) może być liczbą całkowitą (przyjmujemy tu założenie które udowodnimy później, że dwie liczby poddawane temu samemu przekształceniu mają te same współczynniki \(\displaystyle{ \beta(k)}\)):
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+1) \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} + \frac {2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}} \not\in N}\)
. . .
. . .
. . .
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2^{i}-1) \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} + \frac {(2^{i}-1) \cdot 2,5^{a_{1}+...+a_{n}}}{2^{w+x-v}} \not\in N}\)
Analogicznie warunku nie spełniają pozostałe liczby (spełnia go dopiero liczba \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}+2^{i}}\)). Dowodzi to naszego twierdzenia, że każda z wariacji bez powtórzeń dla dowolnego zbioru \(\displaystyle{ 2^{i}}\) liczb następujących po sobie ma realizację w ciągu dokładnie jeden raz, ponieważ wiemy, że przekształcenia w ciągu "5x+1" nie mogą nas wyprowadzać poza zbiór liczb \(\displaystyle{ N}\).
4. Twierdzenie: dwie dowolne liczby poddawane w ciągu temu samemu przekształceniu (tj. wykonywane są na nich te same działania w tej samej kolejności) mają te same współczynniki \(\displaystyle{ \beta(k)}\).
Dowód:
Aby udowodnić słuszność tego twierdzenia wystarczy wykazać, iż współczynniki \(\displaystyle{ \beta(k)}\) zależą wyłącznie od tego w jakiej kolejności i jakie działania wykonujemy na liczbach (a nie od wielkości liczb). Weźmy dowolną liczbę naturalna \(\displaystyle{ g}\) oraz zdefiniujmy dla niej pewien dowolny ciąg przekształceń:
\(\displaystyle{ \left(\frac {\frac {g \cdot 2,5^{a_{1}}+\frac{5}{6} \cdot 2,5^{a_{1}-1}- \frac{1}{3}}{2^{x_{1}}} \cdot 2,5^{a_{2}}+\frac {5}{6} \cdot 2,5^{a_{2}-1}-\frac {1}{3}}{2^{x_{2}}} \cdot \ldots \cdot 2,5^{a_{n}}+\frac {5}{6} \cdot 2,5^{a_{n}-1}-\frac {1}{3}}\right)/2^{x_{n}} = g \cdot \frac {2,5^{a_{1}+...+a_{n}}}{2^{x_{1}+...+x_{n}}} + \frac {(\frac {5}{6} \cdot 2,5^{a_{1}-1}-\frac {1}{3}) \cdot 2,5^{a_{2}+...+a_{n}}}{2^{x_{1}+...+x_{n}}} + \frac {(\frac {5}{6} \cdot 2,5^{a_{2}-1}-\frac {1}{3}) \cdot 2,5^{a_{3}+...+a_{n}}}{2^{x_{2}+...+x_{n}}} + ... + \frac {(\frac {5}{6} \cdot 2,5^{a_{n}-1}-\frac {1}{3})}{2^{x_{n}}} \in N}\)
Zauważmy, że:
\(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2,5^{a_{1}}+\frac {5}{6} \cdot 2,5^{a_{1}-1}- \frac {1}{3} = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \underbrace {\cdot 2,5+0,5) \cdot 2,5+0,5\ldots}_{a \ razy} = 5^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}}\)
Współczynnik \(\displaystyle{ \beta(k)}\) wynosi zatem:
\(\displaystyle{ \beta(k) = \frac {(\frac{5}{6} \cdot 2,5^{a_{1}-1}-\frac {1}{3}) \cdot 2,5^{a_{2}+...+a_{n}}}{2^{x_{1}+...+x_{n}}} + \frac{(\frac {5}{6} \cdot 2,5^{a_{2}-1}- \frac {1}{3}) \cdot 2,5^{a_{3}+...+a_{n}}}{2^{x_{2}+...+x_{n}}} + ... + \frac{(\frac {5}{6} \cdot 2,5^{a_{n}-1}-\frac {1}{3})}{2^{x_{n}}}}\)
Widać zatem, że \(\displaystyle{ \beta(k)}\) zależy wyłącznie od tego w jakiej kolejności, ile i jakie działania zostały wykonanie na liczbie \(\displaystyle{ g}\), natomiast jest niezależny od wielkości \(\displaystyle{ g}\) (ponieważ nie zależy od współczynników \(\displaystyle{ k_{j}}\) które odpowiadają za wielkość liczb).
Łatwo można zauważyć, iż liczb spełniających powyższe równania jest nieskończenie wiele i są one postaci:
\(\displaystyle{ g = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} + 2^{i} \cdot r}\) , \(\displaystyle{ r = 0, 1, 2, ...}\)
5. Twierdzenie: w ciągu "5x+1" przy danej długości ciągu i cyklicznie powtarzają się te same sekwencje przekształceń i następuje to co okres \(\displaystyle{ 2^{i}}\) liczb.
Dowód:
Dowodzi tego zapisany już powyżej wzór:
\(\displaystyle{ g = (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} + 2^{i} \cdot r}\)
wynika z niego, że:
\(\displaystyle{ ((2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w} + 2^{i} \cdot r) \cdot \alpha(k) + \beta(k) = (2^{p} \cdot \frac {q}{3}-\frac {1}{3}) \cdot 2^{v} + 5^{a_{1}+...+a_{n}} \cdot r \in N}\)
Możemy z niego łatwo wyznaczyć także wartości \(\displaystyle{ i-tych}\) iteracji dla liczb przesuniętych od liczby \(\displaystyle{ (2^{a_{1}} \cdot \frac {k_{1}}{3}-\frac {1}{3}) \cdot 2^{w}}\) o dowolną wielokrotność \(\displaystyle{ 2^{i}}\) (czyli o \(\displaystyle{ 2^{i} \cdot r}\)).
6. Twierdzenie: suma współczynników \(\displaystyle{ \alpha(k)}\) w poszczególnych wierszach na przedziałach \(\displaystyle{ 2^{i}}\) kolejnych liczb jest stała i wynosi \(\displaystyle{ 3^{i}}\).
Dowód: twierdzenie to wynika bezpośrednio ze wzoru II. 2. oraz z twierdzenia II. 3.
III. Rozbieżność do nieskończoności ciągu "5x+1".
1. Rozważmy różne (tj. nierówne arytmetycznie) współczynniki \(\displaystyle{ \alpha(k)}\) na przedziale liczb \(\displaystyle{ (1; 2^{i})}\) dla \(\displaystyle{ i-tej}\) iteracji. Zauważmy, iż jest ich \(\displaystyle{ i+1}\).
Twierdzenie: dla \(\displaystyle{ i}\) dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) ilość różnych współczynników \(\displaystyle{ \alpha(k)}\) większych od 1 wynosi \(\displaystyle{ (i+1) \cdot \frac {ln(2)}{ln(5)}}\).
Dowód:
Aby sobie to uświadomić weźmy skończony \(\displaystyle{ (i+1)}\) - wyrazowy ciąg którego kolejne wyrazy zmieniają się jak różne współczynniki \(\displaystyle{ \alpha(k)}\):
\(\displaystyle{ c_1=\frac {5^0}{2^i}}\)
\(\displaystyle{ c_2=\frac {5^1}{2^i}}\)
\(\displaystyle{ c_3=\frac {5^2}{2^i}}\)
\(\displaystyle{ c_4=\frac {5^3}{2^i}}\)
...
\(\displaystyle{ c_{(i+1)}=\frac {5^i}{2^i}}\)
W tym ciągu istnieje pewien wyraz graniczny \(\displaystyle{ c_{g}}\) poniżej którego wszystkie wyrazy są mniejsze od 1 i powyżej którego wszystkie są większe od 1 i który sam jest też większy od 1. Szukamy granicy:
\(\displaystyle{ \lim_{i+1\to\infty} \frac {i+1}{g}}\)
Przy czym \(\displaystyle{ g}\) to numer wyrazu granicznego. Mamy zatem ciąg:
\(\displaystyle{ c(i,k)=\frac{5^i}{2^k}}\)
gdzie \(\displaystyle{ k}\) to pewna stała, szukamy największego takiego \(\displaystyle{ i}\) że:
\(\displaystyle{ c(i,k)>1}\)
logarytmujemy sobie stronami:
\(\displaystyle{ \ln c(i,k)>0}\)
czyli:
\(\displaystyle{ \ln 5^i - \ln 2^k>0\\
i\ln 5 > k\ln 2 \\
i > k \frac{\ln 2}{\ln 5}}\)
Najmniejszym takim całkowitym \(\displaystyle{ i}\) jest oczywiście:
\(\displaystyle{ i_g=\left\lfloor k \frac{\ln 2}{\ln 5} \right\rfloor+1}\)
Teraz chcemy znaleźć granicę:
\(\displaystyle{ \lim_{k\to \infty} \frac{k+1}{i_g}=\lim_{k\to \infty} \frac{k+1}{\left\lfloor k \frac{\ln 2}{\ln 5} \right\rfloor+1}}\)
Szacujemy ją z 3 ciągów i dostajemy granicę:
\(\displaystyle{ \frac {ln(5)}{ln(2)}}\)
2. Rozważmy wszystkie współczynniki \(\displaystyle{ \alpha(k)}\) na przedziale liczb \(\displaystyle{ (1; 2^{i})}\) dla \(\displaystyle{ i-tej}\) iteracji. Zauważmy, iż jest ich \(\displaystyle{ 2^{i}}\).
Twierdzenie: dla \(\displaystyle{ i}\) dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) gęstość współczynników \(\displaystyle{ \alpha(k)}\) większych od 1 jest równa \(\displaystyle{ 2^{i}}\) (zachodzi tu asymptotyczna równość).
Dowód:
Zauważmy, że częstości występowania poszczególnych różnych \(\displaystyle{ i-tych}\) współczynników \(\displaystyle{ \alpha(k)}\) są zadane wartościami liczb w danym \(\displaystyle{ i-tym}\) wierszu trójkąta Pascala. Wobec tego należy obliczyć następującą granicę:
\(\displaystyle{ \lim_{i\to\infty} \frac {\sum_{k=0}^{[\frac {ln(2) \cdot i}{ln(5)}]} {i\choose k}}{2^{i}}=1}\)
Wyrażenie w mianowniku to suma wszystkich współczynników na przedziale \(\displaystyle{ (1; 2^{i})}\) dla \(\displaystyle{ i-tej}\) iteracji, natomiast wyrażenie w mianowniku określa ilość współczynników \(\displaystyle{ \alpha(k)}\) mniejszych od 1 (kolejne współczynniki trójkąta Pascala obliczane z dwumianu Newtona). Wynosi ona 1, zatem dla \(\displaystyle{ i}\) dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) gęstość współczynników \(\displaystyle{ \alpha(k)}\) mniejszych od 1 jest równa \(\displaystyle{ 2^{i}}\).
Dowód:
Szukamy dowodu twierdzenia, że dla rozkładu dwumianowego przy ilości prób \(\displaystyle{ n}\) dążącej do nieskończoności i \(\displaystyle{ p=0,5}\) suma jego wartości od wartości pierwszej do wartości \(\displaystyle{ n \cdot (0,5+y)}\) podzielona przez sumę wszystkich wartości (od 1 do \(\displaystyle{ n}\)) czyli przez \(\displaystyle{ 2^{n}}\) dąży do 1. Przy czym \(\displaystyle{ y}\) to dowolna stała większa od 0 i mniejsza od 0,5 (w naszym przypadku \(\displaystyle{ y}\) jest ujemne, ale to nie ma znaczenia ze względu na symetryczność rozkładu normalnego dla tak przyjętego prawdopodobieństwa).
Rozkład dwumianowy, gdy liczba prób \(\displaystyle{ n}\) dąży do nieskończoności jest zbieżny do rozkładu normalnego \(\displaystyle{ N\sim\left(np, \sqrt{np\left(1-p\right)\right)}}\). Można zatem zbadać ile wynosi ta granica dla rozkładu normalnego przy \(\displaystyle{ \mu=n \cdot 0,5}\) oraz \(\displaystyle{ \sigma=\sqrt{n \cdot 0,25}}\). Rozkład normalny dany jest wzorem:
\(\displaystyle{ f(\mu,\sigma,x) = \frac {1} {\sigma \cdot (2 \pi)^{0,5}} \cdot e^{\frac {-(x-\mu)^{2}}{2 \cdot (\sigma)^{2}}}}\)
A w naszym przypadku:
\(\displaystyle{ f\left(x, n\right) = \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}}}\)
Należy zatem obliczyć granicę:
\(\displaystyle{ \lim_{n\to\infty} \frac {\int\limits_{-\infty}^{(0,5+y) \cdot n} \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}} dx} {\int\limits_{-\infty}^{n} \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}} dx}}\)
I udowodnić, że wynosi ona \(\displaystyle{ 1}\), dla każdego \(\displaystyle{ 0<y<0,5}\).
Całka z \(\displaystyle{ f(x,n)}\) wynosi:
\(\displaystyle{ \int\limits_{-\infty}^{\left(0,5+y\right) \cdot n} \frac {1} {\sqrt{0,25 \cdot n} \cdot \sqrt{2 \pi}} \cdot e^{\frac {-\left(x-0,5 \cdot n\right)^{2}}{0,5 \cdot n}} \text{d}x = 0,5 \cdot \mathrm{erf} \left(\frac {\sqrt{2}} {2} \cdot \sqrt{n}\right) + 0,5 \cdot \mathrm{erf} \left(\sqrt{2} \cdot y \cdot \sqrt{n}\right) + 0,5 \cdot erfc\left(\frac {\sqrt{n}}{\sqrt{2}}\right)}\)
Druga całka wynosi oczywiście 1, zatem liczymy granicę:
przyjmujemy \(\displaystyle{ y=0,5-\frac {ln(2)}{ln(5)}}\)
\(\displaystyle{ \lim_{n\to\infty} \left(0,5 \cdot \mathrm{erf} \left(\frac {\sqrt{2}} {2} \cdot \sqrt{n}\right) + 0,5 \cdot \mathrm{erf} \left(\sqrt{2} \cdot y \cdot \sqrt{n}\right) + 0,5 \cdot erfc\left(\frac {\sqrt{n}}{\sqrt{2}}\right)\right)=1}\)
3. Twierdzenie: zbiór liczb nierozbieżnych do nieskończoności w ciągu „5x+1” ma gęstość 0.
Wynika z twierdzenia III. 2. Skoro dla i dążącego do nieskończoności na przedziale \(\displaystyle{ (1; 2^{i})}\) gęstość współczynników \(\displaystyle{ \alpha(k)}\) większych od 1 jest równa \(\displaystyle{ 2^{i}}\) (oraz przyjmują one rozkład normalny), to zbiór liczb właśnie o gęstości \(\displaystyle{ 2^{i}}\) (przy \(\displaystyle{ i}\) dążącym do nieskończoności) jest rozbieżny do nieskończoności. Rozbieżność zachodzi już dla współczynników \(\displaystyle{ \alpha(k)}\). A skoro zachodzi dla \(\displaystyle{ \alpha(k)}\), to tym bardziej zachodzi dla \(\displaystyle{ r\alpha(k)}\), ponieważ \(\displaystyle{ r\alpha(k)>\alpha(k)}\).
Będę wdzięczny za wszelkie uwagi.
-- 3 stycznia 2012, 16:44 --
Gwoli ścisłości zgodnie z książką "The ultimate challenge: the 3x+1 problem" - Jeffrey'a C. Lagarias'a hipoteza, że każda liczba w ciągu "5x+1" zbiega do jedynki nosi nazwę hipotezy "5x+1" Kakutaniego.
-- 3 stycznia 2012, 17:01 --
To jednak błąd. Kakutani postawił nieco inną hipotezę.matemix pisze: -- 3 stycznia 2012, 16:44 --
Gwoli ścisłości zgodnie z książką "The ultimate challenge: the 3x+1 problem" - Jeffrey'a C. Lagarias'a hipoteza, że każda liczba w ciągu "5x+1" zbiega do jedynki nosi nazwę hipotezy "5x+1" Kakutaniego.