Ciąg Collatza - hipoteza

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
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

Ciąg Collatza - hipoteza

Post autor: matemix »

Czy to prawda, że w ciągu collatza:

\(\displaystyle{ f(x) = \left\{\begin{array}{l} \frac {3x+1}{2} \ \ \ gdy \ x \ nieparzyste\\ \ \ \frac {x}{2} \ \ \ \ \ \ \ gdy \ x \ parzyste \end{array}\right.}\)

istnieje jedna liczba która ma czas stopu \(\displaystyle{ 1}\), jedna która ma czas stopu \(\displaystyle{ 2}\), natomiast ilość liczb \(\displaystyle{ i}\) które mają czas stopu \(\displaystyle{ cs>2}\) określa wzór:

\(\displaystyle{ i=cs-2}\)

Ze wzoru wynika, że przykładowo liczb które mają czas stopu \(\displaystyle{ cs=10}\) jest \(\displaystyle{ i=8}\), itd.

PS Zapewne trudno zweryfikować tą hipotezę analitycznie, ale może ktoś jest w stanie podać kontrprzykład.
Awatar użytkownika
silicium2002
Użytkownik
Użytkownik
Posty: 786
Rejestracja: 9 lip 2009, o 15:47
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy
Pomógł: 114 razy

Ciąg Collatza - hipoteza

Post autor: silicium2002 »

Hm, jak się tak zastanawiam. To jeżeli dla tego przykładowego \(\displaystyle{ cs=10}\)mielibyśmy \(\displaystyle{ i=8}\), to wtedy rozpatrzmy osiem liczb utworzonych w ten sposób że te o \(\displaystyle{ cs=10}\) przemnożymy przez 2. Wtedy dla nich cs wynosiłoby \(\displaystyle{ 11}\). Stąd wśród liczb o \(\displaystyle{ cs=11}\), których powinno być 9, osiem byłoby parzystych - a więc jedna i dokładnie jedna byłaby nieparzysta. Takie rozumowanie można zastosować dla dowolnego cs - a więc wynikałoby z twojej hipotezy, że dowolne dwie liczby nieparzyste mają różne cs.

Zagłębiając się dalej - załóżmy że istnieje wśród tych ośmiu liczb o \(\displaystyle{ cs=10}\) liczba postaci \(\displaystyle{ 3k+1}\) dla k nieparzystego.Wtedy Zauważmy że liczba \(\displaystyle{ k}\) ma również \(\displaystyle{ cs=11}\). Stąd wniosek, że może być maksymalnie jedna taka liczba dla zadanego cs.

Z pewnością da się to jakoś dalej pociągnąć.

A chyba dość łatwym pokazaniem byłoby znalezienie dwóch liczb nieparzystych o jednakowym cs.
matemix
Użytkownik
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

Ciąg Collatza - hipoteza

Post autor: matemix »

Nie wiem, czy o to Ci chodziło, ale potwierdzenie hipotezy sprowadza się, do udowodnienia, że istnieje dokładnie jedna liczba nieparzysta o danym \(\displaystyle{ cs}\) (rozpatrujemy tylko \(\displaystyle{ cs>3}\)). Jeżeli tak by było, to mając pewną ilość liczb o danym czasie stopu wystarczy je pomnożyć razy 2 i dostaniemy tą samą ilość liczb (wszystkie parzyste) o czasie stopu dłuższym o jeden. Teraz wystarczy znaleźć jedną dodatkową liczbę nieparzystą (i tylko jedną) o czasie dłuższym o jeden od poprzedniego rozpatrywanego i dostaniemy ilość liczb o czasie stopu dłuższym o jeden od poprzedniego rozpatrywanego dokładnie taką jak przewiduje hipoteza. Jeżeli dla dowolnego \(\displaystyle{ cs>3}\) znajdziemy jedną i tylko jedną liczbę nieparzystą o takim właśnie czasie stopu, to indukcyjnie wynika z tego prawdziwość hipotezy.

Można wykazać, że na pewno istnieje taka liczba nieparzysta, gdy \(\displaystyle{ cs=2k-1}\) są nieparzyste. Liczby te są postaci:

dla \(\displaystyle{ k=3}\) \(\displaystyle{ , c_{1}=3}\)
dla \(\displaystyle{ k>3}\):

\(\displaystyle{ c_{n}=3+10 \cdot \sum_{i=0}^{k-4} 4^{i}}\)

Można to udowodnić pokazując, że wykonanie następujących działań na liczbach \(\displaystyle{ c_{n}}\) daje liczbę \(\displaystyle{ 1}\):

\(\displaystyle{ (((c_{n} \cdot 1,5+0,5)/2^{2k-6}) \cdot 1,5+0,5)/8=1}\)

Można także wykazać, że na pewno istnieje taka liczba nieparzysta, gdy \(\displaystyle{ cs=2k}\) są parzyste. Liczby te są postaci:

\(\displaystyle{ c_{n}=\sum_{i=0}^{k-1} 4^i}\)

W tym przypadku można to udowdnić jeszcze szybciej pokazując, że wykonanie następujących działań na liczbach \(\displaystyle{ c_{n}}\) daje liczbę \(\displaystyle{ 1}\):

\(\displaystyle{ (c_{n} \cdot 1,5+0,5)/^{2k-1}=1}\)


Potwierdza to zatem, że dla danego czasu stopu na pewno znajdziemy co najmniej tyle liczb ile przewiduje wzór. Pozostaje zatem udowdnić, że nie będzie ich więcej, czyli sprawdzić czy istnieje dokładnie jedna (nie więcej) liczba nieparzysta o danym \(\displaystyle{ cs}\).-- 25 maja 2012, 01:29 --Wygląda na to, że hipoteza jest jedna fałszywa. Można znaleźć dwie liczby nieparzyste o takim samym czasie stopu, np. \(\displaystyle{ 7}\) i \(\displaystyle{ 213}\).
eMaerthin
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 12 paź 2011, o 19:03
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 10 razy

Ciąg Collatza - hipoteza

Post autor: eMaerthin »

Ciekawa hipoteza, choć zbyt prosta żeby była prawdziwa. Nie zrażaj się i szukaj tutaj zależności. Wśród liczb nieparzystych do 20001 istnieją dwie o cs=9, cztery o cs=10, sześć o cs=11.
Pierwszą parą kolejnych liczb nieparzystych o takim samym cs są 49 i 51. Ich cs=17. Pierwszą trójkę kolejnych liczb nieparzystych o takim samym cs stanowią 343,345,347. Ich cs=80.
matemix
Użytkownik
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

Ciąg Collatza - hipoteza

Post autor: matemix »

Generalnie dobre przybliżenie tego ile jest liczb o danym takim samym czasie stopu i jakiej wielkości są one mniej więcej powinien dawać (przybliżony, teoretyczny) wzór na \(\displaystyle{ cs}\) liczby \(\displaystyle{ n}\):

\(\displaystyle{ cs = \frac {2}{ln(\frac {4}{3})} \cdot ln(n)}\)

który prawdopodobnie jest zbieżny do czasu stopu liczb w ciągu collatza (a dokładnie do logarytmicznej krzywej regresji czasu stopu).
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Re: Ciąg Collatza - hipoteza

Post autor: mol_ksiazkowy »

film The Simplest Math Problem No One Can Solve - Collatz Conjecture

Kod: Zaznacz cały

youtube.com/watch?v=094y1Z2wpJg
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Ciąg Collatza - hipoteza

Post autor: Brombal »

Pierwszy raz o tym usłyszałem - sprawdziłem w Wikipedii. Wygląda na to że wzór jest \(\displaystyle{ 3\cdot x+1}\) tu jest podany \(\displaystyle{ \frac{3\cdot x+1}{2} }\)
Wygląda, że istotny w temacie i narzucający się natychmiast jest stopień parzystości liczby.
Każda liczbę naturalna można przedstawić w postaci \(\displaystyle{ x=a\cdot 2^{s} }\) gdzie \(\displaystyle{ a}\)-nieparzysta, \(\displaystyle{ s}\) -stopień parzystości.
stad kolejne \(\displaystyle{ sc}\) dla \(\displaystyle{ 7}\) to \(\displaystyle{ 14, 28, 56, ....3584,...}\) przyrastają po jednym oczku.
Ostatnio zmieniony 1 sie 2022, o 20:08 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

Re: Ciąg Collatza - hipoteza

Post autor: 3a174ad9764fefcb »

Brombal pisze: 1 sie 2022, o 08:33 Wygląda na to że wzór jest \(\displaystyle{ 3*x+1}\) tu jest podany \(\displaystyle{ \frac{3*x+1}{2} }\)
Nie ma to większego znaczenia. Hipoteza z jednym wzorem jest równoważna hipotezie z drugim.
matemix
Użytkownik
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

Re: Ciąg Collatza - hipoteza

Post autor: matemix »

Dużo czasu minęło od momentu założenia tego wątku, a ja przeczytałem setki publikacji na temat ciągu Collatza. Heurystyczny wzór, który znalazłem zaraz po zadaniu pytania jest nie tylko aktualny i jest najlepszym przybliżeniem oczekiwanej liczby kroków, po których liczba osiąga jedynkę w ciągu Collatza jaki mamy, ale został wyznaczony już dawno przez innych matematyków (np. Crandalla i Shanksa, jak opisuje to Lagarias w "The 3x+1 Problem and its Generalizations"):

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

Są odstępstwa od tego wzoru. Np. liczba \(\displaystyle{ n=7219136416377236271195}\) osiąga jedynkę dopiero po \(\displaystyle{ 36.7169 \cdot \ln(n)}\) krokach. Stochastyczne modele przewidują natomiast, że to odstępstwo od oczekiwanej liczby kroków wyznaczonej przez powyższy wzór nie może przekraczać \(\displaystyle{ 41.677647 \cdot \ln(n)}\). Lagarias postuluje nawet ("THE 3x + 1 PROBLEM: AN OVERVIEW"), że problem, czy istnieje liczba, która nie osiąga jedynki po \(\displaystyle{ 100 \cdot \ln(n)}\) może być nierozstrzygalny.
mol_ksiazkowy pisze: 27 lip 2022, o 22:47 film The Simplest Math Problem No One Can Solve - Collatz Conjecture

Kod: Zaznacz cały

youtube.com/watch?v=094y1Z2wpJg
Świetny filmik.

Po latach uważam, że ten problem Collatza jest nierozstrzygalny, podobnie jak generalizacje rozpatrywane przez Conwaya. Ciągi Collatza wydają się być przykładem ekstremalnie zbiasowanego generatora liczb losowych, w którym jako ziarna możemy traktować kolejne liczby naturalne. Ponieważ generator ma wbudowany bias, liczby wpadają w pętle, ale jednocześnie ponieważ realizuje także proces stochastyczny pewne jego bity (najmniej znaczące bity iterowanych liczb) są zupełnie losowe (dopóki generator nie wpadnie w pętlę). Jeżeli prawdziwe jest założenie o losowości, to możemy mówić tylko o prawdopodobieństwie, nie o dowodzie, inaczej wykluczona jest losowość.

Ciąg Collatza wykonuje operacje typu \(\displaystyle{ 1,5 \cdot x + 0,5}\) lub \(\displaystyle{ \frac{x}{2}}\) w losowej kolejności, a zatem wszystkie liczby powinny dążyć do jedynki lub do jakiejś pętli. Podobno w 2005 roku Freeman Dyson został zapytany: “What do you believe is true even though you cannot prove it?” i odpowiedział:
Since I am a mathematician, I give a precise answer to this question. Thanks to Kurt Godel, we know that there are true mathematical statements that cannot be proved. But I want a little more than this. I want a statement that is true, unprovable, and simple enough to be understood by people who are not mathematicians. Here it is.

Numbers that are exact powers of two are 2, 4, 8, 16, 32, 64, 128 and so on. Numbers that are exact powers of five are 5, 25, 125, 625 and so on. Given any number such as 131072 (which happens to be a power of two), the reverse of it is 270131, with the same digits taken in the opposite order. Now my statement is: it never happens that the reverse of a power of two is a power of five.

The digits in a big power of two seem to occur in a random way without any regular pattern. If it ever happened that the reverse of a power of two was a power of five, this would be an unlikely accident, and the chance of it happening grows rapidly smaller as the numbers grow bigger. If we assume that the digits occur at random, then the chance of the accident happening for any power of two greater than a billion is less than one in a billion. It is easy to check that it does not happen for powers of two smaller than a billion. So the chance that it ever happens at all is less than one in a billion. That is why I believe the statement is true.

But the assumption that digits in a big power of two occur at random also implies that the statement is unprovable. Any proof of the statement would have to be based on some non-random property of the digits. The assumption of randomness means that the statement is true just because the odds are in its favor. It cannot be proved because there is no deep mathematical reason why it has to be true. (Note for experts: this argument does not work if we use powers of three instead of powers of five. In that case the statement is easy to prove because the reverse of a number divisible by three is also divisible by three. Divisibility by three happens to be a non-random property of the digits).

It is easy to find other examples of statements that are likely to be true but unprovable. The essential trick is to find an infinite sequence of events, each of which might happen by accident, but with a small total probability for even one of them happening. Then the statement that none of the events ever happens is probably true but cannot be proved.
Podaje więc przykład podobnego problemu. Rozstrzygnięcie, czy generatory liczb pseudo-losowych w ogóle istnieją w kontekście jakichś klas złożoności, to problem ściśle powiązany z problemem P versus NP. Gdybym był matematykiem albo miał komuś coś doradzić, nawet nie zaczynałbym szukać w tym jakichś kolejnych arytmetycznych wzorców, tylko od razu skupił się na próbie rozstrzygnięcia lub jednoznacznego wykluczenia, że ciągi realizują proces stochastyczny. Sprawa w tej chwili wydaje się ewidentna, zdaje się tylko, że nie mamy narzędzi, żeby ktoś przyszedł i mógł powiedzieć - tak, pod pewnymi warunkami ciągi Collatza są generatorami liczb losowych, nie istnieje metoda przewidzenia zachowania się ciągów dla każdej liczby naturalnej.

Dodano po 1 dniu 11 godzinach 21 sekundach:
Dodam jeszcze, że to samo pisze Lagarias w jednym ze swoich najnowszych przeglądów "THE 3x + 1 PROBLEM: AN OVERVIEW":
The iterates of the shift function are completely unpredictable in the ergodic theory sense. Given a random starting point, predicting the parity of the n-th iterate for any n is a “coin flip” random variable.
Empirical evidence seems to indicate that the 3x + 1 function on the domain Z retains the “pseudorandomness” property on its initial iterates until the iterates enter a periodic orbit. This supports the 3x + 1 conjecture and at the same time deprives us of any obvious mechanism to prove it, since mathematical arguments exploit the existence of structure, rather than its absence.
Losowy proces, zanim wpadnie w pętlę i tak jak w przykładzie Dysona, losowy mechanizm, który z jednej strony wspiera prawdziwość hipotezy, a z drugiej oddala nas od możliwości sformułowania dowodu.
Ostatnio zmieniony 10 sie 2022, o 16:08 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd.
ODPOWIEDZ