Ciąg "x"

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 "x"

Post autor: matemix »

Weźmy dowolną liczbę naturalną \(\displaystyle{ x_{0}}\) (większą od 0). Jeśli jest ona parzysta, to za \(\displaystyle{ x_{1}}\) przyjmijmy \(\displaystyle{ x_{0}/2}\), natomiast jeśli jest nieparzysta to niech \(\displaystyle{ x_{1}= \sum_{i=1}^{x_{0}} i}\). Następnie, z liczbą \(\displaystyle{ x_{1}}\) postępujemy podobnie jak z \(\displaystyle{ x_{0}}\) i kontynuujemy ten proces. Otrzymamy w ten sposób ciąg liczb naturalnych określony przez formułę:

\(\displaystyle{ x_{n+1} = \begin{cases}\frac {1}{2} x_{n} \quad \quad \qquad gdy \quad x_{n} \quad jest \quad parzysta



\\ \sum_{i=1}^{x_{n}} i \qquad gdy \quad x_{n} \quad jest \quad nieparzysta \end{cases}}\)




Prawdopodonie ciąg jest rozbieżny do nieskończoności dla dowolnej liczby \(\displaystyle{ x_{n}}\), poza liczbami które zapętlają się w pętlach trywialnych które występują dla liczb \(\displaystyle{ x_{n}}\) postaci \(\displaystyle{ 2^{t}-1}\) oraz liczbami które wpadają w te pętle.



Pytanie czy jedynymi pętlami które występują w ciągu są pętle trywialne i czy rzeczywiście dla każdej liczby naturalnej (poza liczbami które się zapętlają i które wpadają w pętle) ciąg jest rozbieżny do nieskończoności?



Przykłady:

Liczba 7 zapętla się: 7, 28, 14, 7, 28, 14, itd.

Liczba 5 wpada w pętlę liczby 15: 5, 15, 120, 60, 30, 15, 120, 60, 30, 15, 120, itd.

Liczba 11 jest prawdopodobnie rozbieżna do nieskończoności: 11, 66, 33, 561, 157641, 12425421261, 7,72E+019, 3,86E+019, 1,93E+019...



Liczba 5 wpada w pętlę trywialną, ponieważ spełnia równanie:

\(\displaystyle{ \frac {x_{0}^{2}+x_{0}}{2^{k}}=2^{t}-1}\)

Aby stwierdzić, czy jescze jakieś liczby (nieparzyste) mogą wpadać w pętle trywialne, czy też piątka jest jedyną tego rodzaju liczbą należy sprawdzić, czy równanie (oraz ciąg równań w poście poniżej) może być spełnione dla innych parametrów.
Ostatnio zmieniony 14 maja 2010, o 04:49 przez matemix, łącznie zmieniany 3 razy.
Xitami

Ciąg "x"

Post autor: Xitami »

1,2,3,4,5,6,7,8,10,12,14,15,16,20,24,28,30,31,32,40,48,56,60,62,63,64,
80,96,112,120,124,126,127,128,160,192,224,240,248,252,254,255,256,
320,384,448,480,496,504,508,510,511,512,640,768,896,960,992,

liczby <1000 które prowadzą do okresu, inne rosną okropnie, przerywałem po przekroczeniu 10^100'000
Neil ich nie zna :-)
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 "x"

Post autor: matemix »

Xitami pisze:1,2,3,4,5,6,7,8,10,12,14,15,16,20,24,28,30,31,32,40,48,56,60,62,63,64,
80,96,112,120,124,126,127,128,160,192,224,240,248,252,254,255,256,
320,384,448,480,496,504,508,510,511,512,640,768,896,960,992,

liczby <1000 które prowadzą do okresu, inne rosną okropnie, przerywałem po przekroczeniu 10^100'000
Neil ich nie zna :-)
Oczywiście są to liczby nieparzyste postaci \(\displaystyle{ 2^{t}-1}\) oraz parzyste postaci \(\displaystyle{ 2^{p} \cdot (2^{t}-1)}\). Do tego dochodzą wszystkie liczby \(\displaystyle{ x_{0}}\) spełniające równanie:

\(\displaystyle{ \frac {x_{0}^{2}+x_{0}}{2}=2^{t}-1}\)

oraz liczby \(\displaystyle{ 2^{p} \cdot x_{0}}\).

Jakkolwiek wszystkie te ciągi wpadają w pętle trywialne, niespodzianką byłoby odkrycie pętli nietrywialnej.

-- 13 maja 2010, 20:26 --

Cóż, jeśli chodzi o liczby które wpadają w ciągi trywialne, to pomyliłem się. Nie są to tylko liczby spełniające poniższe równanie:

\(\displaystyle{ \frac {x_{0}^{2}+x_{0}}{2^{k}}=2^{t}-1}\)

ale także liczby spełniające te nieskończenie wiele równań:

\(\displaystyle{ \frac {(\frac {x_{0}^{2}+x_{0}}{2^{k}})^{2}+\frac {x_{0}^{2}+x_{0}}{2^{k}}}{2^{k}}=2^{t}-1}\)

\(\displaystyle{ \frac {(\frac {(\frac {x_{0}^{2}+x_{0}}{2^{k}})^{2}+\frac {x_{0}^{2}+x_{0}}{2^{k}}}{2^{k}})^{2}+\frac {(\frac {x_{0}^{2}+x_{0}}{2^{k}})^{2}+\frac {x_{0}^{2}+x_{0}}{2^{k}}}{2^{k}}}{2^{k}}=2^{t}-1}\)

itd. oraz liczby \(\displaystyle{ 2^{p} \cdot x_{0}}\).
Ostatnio zmieniony 13 maja 2010, o 21:59 przez matemix, łącznie zmieniany 1 raz.
Xitami

Ciąg "x"

Post autor: Xitami »

Ni jestem pewny, co rozumiesz przez nietrywialną?
2,2 (1)
3,(3 6)
4,4 2 (1)
5,5 (15 120 60 30)
6,(6 3)
7,(7 28 14)
8,8 4 2 (1)
10,10 5 (15 120 60 30)
12,12 (6 3)
14,(14 7 28)
15,(15 120 60 30)
16,16 8 4 2 (1)
20,20 10 5 (15 120 60 30)
24,24 12 (6 3)
28,(28 14 7)
30,(30 15 120 60)
31,(31 496 248 124 62)
32,32 16 8 4 2 (1)
40,40 20 10 5 (15 120 60 30)
48,48 24 12 (6 3)
56,56 (28 14 7)
60,(60 30 15 120)
62,(62 31 496 248 124)
63,(63 2016 1008 504 252 126)
64,64 32 16 8 4 2 (1)
80,80 40 20 10 5 (15 120 60 30)
96,96 48 24 12 (6 3)
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 "x"

Post autor: matemix »

Xitami pisze:Ni jestem pewny, co rozumiesz przez nietrywialną?
Pętla trywialna to taka której elementem jest liczba postaci \(\displaystyle{ 2^{t}-1}\), a zatem pętla nietrywialna to taka której elementem nie będzie liczba \(\displaystyle{ 2^{t}-1}\).
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 "x"

Post autor: matemix »

Po chwili zastanowienia doszedłem do wniosku, że jeżeli następujące równanie:

\(\displaystyle{ (c^{2}+c)=2^{i} \cdot (2^{k}-1)}\)

nie ma innych rozwiązań, niż dla \(\displaystyle{ c=5}\), \(\displaystyle{ i=1}\) oraz \(\displaystyle{ k=4}\), takich, że \(\displaystyle{ c}\) nie będzie postaci \(\displaystyle{ 2^{k}-1}\), to jedynymi pętlami jakie występują w ciągu są pętle trywialne (choć to nie ma nic wspólnego z tym równaniem), jedyną liczbą jaka wpada w pętlę (przy czym czym innym jest wpadanie liczby w pętlę, a czym innym zapętlanie się danej liczby) jest liczba \(\displaystyle{ 5}\), a wszystkie pozostałe liczby są rozbieżne do nieskończoności.

Aby wykazać, że jedynymi liczbami jakie zapętlają się w ciągu są liczby postaci \(\displaystyle{ 2^{k}-1}\) (które z definicji generują pętle trywialne) należy napisać pewne równanie diofantyczne. Generalnie operację sumowania danej liczby nieparzystej jak w ciągu można zapisać tak:

\(\displaystyle{ x_{1}= \sum_{i=1}^{x_{0}} i=\frac {x_{0}^{2}+x_{0}}{2}}\)

A zatem zaczynając od liczby nieparzystej \(\displaystyle{ {x_{0}}\) otrzymujemy \(\displaystyle{ \frac {x_{0}^{2}+x_{0}}{2}}\), otrzymaną liczbę dzielimy przez liczbę \(\displaystyle{ 2}\) kilkakrotnie lub raz, a zatem ogólnie dzielimy ją przez jakąś potęgę dwójki. Jeśli po dzieleniu otrzymamy z powrotem liczbę \(\displaystyle{ {x_{0}}\) mamy pętlę. Możemy zatem zapisać warunek pętli:

\(\displaystyle{ \frac {x^{2}+x}{2^{i}}=x}\), czyli \(\displaystyle{ \frac {x^{2}+x}{x}=2^{i}}\)

Taką pętlę nazwiemy pętlą I-ego stopnia. Jednak mogą istnieć również bardziej skomplikowane pętle:

\(\displaystyle{ \frac {x^{2}+x}{x} \cdot \frac {a^{2}+a}{a} \cdot \frac {b^{2}+b}{b} \cdot ... \cdot \frac {n^{2}+n}{n}=2^{t}}\)

Iloraz każdego licznika i następującego po nim mianownika jest zawsze (zgodnie z definicją ciągu) jakąś potęgą dwójki. Wyrażenie opisujące warunek pętli n-tego stopnia skraca nam się do postaci:

\(\displaystyle{ (x+1) \cdot (a+1) \cdot (b+1) \cdot ... \cdot (n+1)=2^{t}}\)

Wynika z tego, iż jedynymi liczbami jakie mogą spełniać warunki pętli są liczby postaci \(\displaystyle{ 2^{k}-1}\), ponad to wszystkie te pętle trywialne są zawsze zaledwie I-ego stopnia, bo każda liczba \(\displaystyle{ 2^{k}-1}\) wrzucona w ciąg zapętla się już przy pierwszym cyklu operacji.


Aby sprawdzić czy jakieś inne liczby niż liczba \(\displaystyle{ 5}\) wpadają w pętle trywialne należy sprawdzić czy jakakolwiek liczba nieparzysta \(\displaystyle{ x}\) (parzystymi nie ma sensu się zajmować, bo i tak redukują się do nieparzystych, więc wystarczy rozpatrzyć tylko nieparzyste) nie będąca postaci \(\displaystyle{ 2^{k}-1}\) wrzucona w ciąg osiągnie w końcu liczbę postaci \(\displaystyle{ 2^{k}-1}\). Stąd równanie:

\(\displaystyle{ x \cdot \frac {x^{2}+x}{x} \cdot \frac {a^{2}+a}{a} \cdot \frac {b^{2}+b}{b} \cdot ... \cdot \frac {(2^{k}-1)^{2}+2^{k}-1}{2^{k}-1}=2^{n} \cdot (2^{k}-1)}\)

Gdy przesuniemy wszystkie mianowniki z lewej strony równania o jedną pozycję pod liczniki je poprzedzające powinniśmy otrzymać właśnie takie wyrażenie jak po prawej stronie, liczby skracają się z racji relacji jakie pomiędzy nimi zachodzą na mocy definicji ciągu. Jednak operując na zmiennych, nie liczbach takie skrócenie oczywiście nic nie wniesie, dlatego póki co można to skrócić do takiej postaci:

\(\displaystyle{ (x^{2}+x) \cdot (a+1) \cdot (b+1) \cdot ... \cdot 2^{k}=2^{n} \cdot (2^{k}-1)}\) i dalej:

\(\displaystyle{ (x^{2}+x) \cdot (a+1) \cdot (b+1) \cdot ... =2^{m} \cdot (2^{k}-1)}\)

Mamy tu niezdefiniowanej długości ciąg który w końcu generuje liczbę postaci \(\displaystyle{ 2^{k}-1}\), jednak nie musimy zajmować się aż tak rozbudowanym równaniem. Jeżeli po liczbie \(\displaystyle{ x}\) w wyniku jakiejś dużej ilości operacji następuje w końcu liczba \(\displaystyle{ c}\) która generuje liczbę postaci \(\displaystyle{ (2^{k}-1)}\), to ta liczba musi spełniać krótsze równanie:

\(\displaystyle{ (c^{2}+c)=2^{i} \cdot (2^{k}-1)}\)

Właśnie dlatego, bo generuje liczbę postaci \(\displaystyle{ (2^{k}-1)}\). I tylko takie równanie wystarczy zbadać. Liczby \(\displaystyle{ x,a,b}\) i inne poprzedzające liczbę \(\displaystyle{ c}\) możemy wygenerować sami (o ile istnieją), gdy będziemy wiedzieli już, że \(\displaystyle{ c}\) spełnia warunki poprzez uwstecznienie ciągu.

Podobną sztuczkę znajdowania liczb spełniających równanie możemy też zastosować do liczby \(\displaystyle{ 5}\). Uwstecznienie liczby będzie polegało najpierw na pomnożeniu ją \(\displaystyle{ n}\) razy \(\displaystyle{ 2}\), a następnie wyznaczeniu dla któregoś \(\displaystyle{ n-tego}\) iloczynu liczby nieparzystej która po zsumowaniu zgodnie z definicją ciągu da właśnie \(\displaystyle{ 2^{n} \cdot 5}\). Szukamy zatem rozwiązań równania:

\(\displaystyle{ \frac {x^{2}+x}{2}=2^{n} \cdot 5}\)

Niestety liczba \(\displaystyle{ 5}\) nie ma poprzedników, ponieważ powyższe równanie nie ma rozwiązań. Aby \(\displaystyle{ x^{2}+x}\) było podzielne przez \(\displaystyle{ 5}\), to \(\displaystyle{ x}\) musi być równe \(\displaystyle{ 9+10p}\) lub \(\displaystyle{ 5+10p}\). Jeżeli \(\displaystyle{ x=9+10p}\), to \(\displaystyle{ \frac {x^{2}+x}{5}}\) jest również podzielne przez samo \(\displaystyle{ x}\), natomiast przez \(\displaystyle{ x}\) (postaci \(\displaystyle{ 9+10p}\)) nie będzie wtedy podzielna prawa strona. Natomiast gdy \(\displaystyle{ x=5+10p}\), to lewa strona jest podzielna przez \(\displaystyle{ x}\), a prawa może być całkowita tylko gdy \(\displaystyle{ \frac {5+10p}{5}=2^{d}}\), a to niemożliwe. Jednakowoż nie wyklucza to tego, że gdyby znalazły się inne rozwiązania równania z pierwszego postu, to być może tamte liczby będą miały poprzedniki.

No i ostatnia kwestia. Dlaczego gdyby okazało się, że równanie z pierwszego postu ma tylko jedno rozwiązanie moglibyśmy mieć pewność, iż wszystkie liczby poza liczbą \(\displaystyle{ 5}\) i liczbami postaci \(\displaystyle{ 2^{k}-1}\) są w naszym ciągu rozbieżne do nieskończoności? To proste - bo zwyczajnie nie ma innej logicznej możliwości. Liczby te nie mogą wtedy wpadać w pętle, ani same się zapętlać. M.in. na tej podstawie możemy mieć pewność, że każdy ciąg dla danej liczby jest różnowartościowy, tzn. żadna liczba nie występuje w nim dwa razy. Jeśli tak to dla danej liczby ciąg musi przyjmować wciąż inne liczby większe od zera, może on po drodze dowolnie rosnąć i maleć, ale ogólnie musi odwoływać się do coraz to większych liczb, bo każdy skończony zbiór nawet wielkich liczb do którego odwołuje się ciąg w końcu się skończy.
ODPOWIEDZ