Dwa ciągi liczbowe i ich okres

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Morfeo
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 8 wrz 2015, o 19:21
Płeć: Mężczyzna
Lokalizacja: z daleka
Podziękował: 1 raz

Dwa ciągi liczbowe i ich okres

Post autor: Morfeo »

Witam serdecznie,

Nie byłem pewny w jakim dziale umieścić temat. Ewentualnie proszę o przeniesienie.

Mam prośbę o dowód poprawności pewnego twierdzenia. Jeżeli nie jest prawidłowe to prośba dotyczy tego wytknięcia

Mamy ciąg liczbowy \(\displaystyle{ a_{i}}\), w którym zawsze występuje cykl. Przykładowo niech będzie to:

\(\displaystyle{ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5...}\)

czyli:

\(\displaystyle{ a_{0} = 1 \\
a_{1} = 2 \\
a_{2} = 3 \\
a_{3} = 4 \\
a_{4} = 5 \\
a_{i} = a_{i \% 5}}\)


Na podstawie tego ciągu generujemy inny ciąg liczbowy \(\displaystyle{ n_{i}}\) według następującej reguły:

\(\displaystyle{ n_{0} = a_{x + k \cdot 0} \\
n_{1} = a_{x + k \cdot 1} \\
n_{2} = a_{x + k \cdot 2} \\
n_{i} = a_{x + k \cdot i}}\)


Dla przykładu weźmy \(\displaystyle{ x = 2}\) i \(\displaystyle{ k = 3}\):

\(\displaystyle{ n_{0} = a_{2 + 3 \cdot 0} = a_{2} = 3 \\
n_{1} = a_{2 + 3 \cdot 1} = a_{5} = 1 \\
n_{2} = a_{2 + 3 \cdot 2} = a_{8} = 4 \\
n_{3} = a_{2 + 3 \cdot 3} = a_{11} = 2 \\
n_{4} = a_{2 + 3 \cdot 4} = a_{14} = 5 \\
n_{5} = a_{2 + 3 \cdot 5} = a_{17} = 3 \\
n_{6} = a_{2 + 3 \cdot 6} = a_{20} = 1}\)

...

Udowodnić należy że ciąg \(\displaystyle{ n_{i}}\) także zawsze jest okresowy dla dowolnego ciągu wejściowego \(\displaystyle{ a_{i}}\) (także okresowego) i dowolnych zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ k}\).

Mam nadzieję, że nigdzie się nie pomyliłem ale jednak jakiś błąd możliwy

Bardzo dziękuję za wszelką pomoc.
Ostatnio zmieniony 15 wrz 2015, o 21:03 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Dwa ciągi liczbowe i ich okres

Post autor: Medea 2 »

Jeżeli ciąg \(\displaystyle{ a_i}\) jest okresowy i jego okres wynosi \(\displaystyle{ t}\), to okresem \(\displaystyle{ n_i}\) również jest \(\displaystyle{ t}\). Uzasadnienie:

\(\displaystyle{ n(i+t) = a(x+k(i+t)) = a(x+ki + kt) = a(x+ki) = n(i)}\).
Ostatnio zmieniony 15 wrz 2015, o 10:53 przez Medea 2, łącznie zmieniany 1 raz.
Morfeo
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 8 wrz 2015, o 19:21
Płeć: Mężczyzna
Lokalizacja: z daleka
Podziękował: 1 raz

Dwa ciągi liczbowe i ich okres

Post autor: Morfeo »

O kurcze - bardzo zwięźle

Ale czy oby dla każdego \(\displaystyle{ x}\) i \(\displaystyle{ k}\) okres \(\displaystyle{ n_{i}}\) będzie wynosił \(\displaystyle{ t}\) (tyle samo co dla \(\displaystyle{ a_{i}}\))?

Weźmy ciąg \(\displaystyle{ a_{i}}\) z pierwszego mojego postu w temacie.
Weźmy \(\displaystyle{ x = 1}\) i \(\displaystyle{ k = 5}\).

Wtedy ciąg \(\displaystyle{ n_{i}}\) będzie następujący: \(\displaystyle{ 2, 2, 2, 2...}\)

Rozmiar okresu = \(\displaystyle{ 1}\) i jest różny od rozmiaru okresu \(\displaystyle{ a_{i}}\).

PS. W dowodzie chodzi tylko o dowód, że istnieje okres \(\displaystyle{ n_{i}}\).
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Dwa ciągi liczbowe i ich okres

Post autor: Medea 2 »

Właśnie. Aby udowodnić, że ciąg jest okresowy, wystarczy podać jego dowolny okres, nie trzeba skupiać się na okresie podstawowym (najmniejszym). Sytuacja przypomina trochę "grube" oszacowania, przykładowo: ciąg \(\displaystyle{ 2^n}\) jest nieograniczony (i rozbieżny do \(\displaystyle{ \infty}\)), bo \(\displaystyle{ 2^n > n}\)
Morfeo
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 8 wrz 2015, o 19:21
Płeć: Mężczyzna
Lokalizacja: z daleka
Podziękował: 1 raz

Dwa ciągi liczbowe i ich okres

Post autor: Morfeo »

Ah. Rozumiem.

Źle chyba jednak sformułowałem pytanie (myśląc tylko o okresie) :/

Chodziło mi raczej o dowód na to, że jeżeli mamy w ciągu \(\displaystyle{ n_{i}}\) wyraz powiedzmy pierwszy \(\displaystyle{ n_{0} = 1}\) i będziemy lecieć po kolejnych wyrazach aż do np. \(\displaystyle{ n_{10}}\), które okaże się także (jako pierwsze następne po \(\displaystyle{ n_{0}}\)) równe \(\displaystyle{ 1}\) to właśnie to będzie cyklem.

Jednym słowem niemożliwy jest cykl np. typu:

\(\displaystyle{ 1, 1, 2, 2, 1, 1, 2, 2...}\)

Zastanawiam się nad tym w kontekście pewnego programu komputerowego, który piszę.

Gdybyśmy mogli uzyskać przykładowo ciąg \(\displaystyle{ n_{i}}\): \(\displaystyle{ 1, 1, 2, 2, 1, 1, 2, 2...}\)

To mój program komputerowy przeszukiwanie zacząłby od \(\displaystyle{ 1}\) i skończył na kolejnej (drugiej) jedynce i na tym doszedł do wniosku, że odnalazł cykl, ponieważ jedynka się powtarza.

Dowód, który przedstawiłaś Medea 2 w drugim poście już jest bardzo pomocny, ponieważ teoretycznie wystarczyłoby, że sprawdziłbym tych \(\displaystyle{ t}\) wyrazów i tam byłby na 100% cykl i ewentualnie wyciągnął z tego mniejsze cykle.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Dwa ciągi liczbowe i ich okres

Post autor: a4karo »

Zobacz, co się stanie jak zaczniesz np od ciagu okresowego \(\displaystyle{ 1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,...}\)
Ostatnio zmieniony 15 wrz 2015, o 21:04 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Morfeo
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 8 wrz 2015, o 19:21
Płeć: Mężczyzna
Lokalizacja: z daleka
Podziękował: 1 raz

Dwa ciągi liczbowe i ich okres

Post autor: Morfeo »

Nie, nie. W ciągu początkowym \(\displaystyle{ a_{i}}\) w samym okresie nie mogą powtarzać się wartości wyrazów więc coś takiego odpada. Zapomniałem o tym napisać za co przepraszam.

\(\displaystyle{ 1, 1, 2, 1, 1, 2...}\) - nie może wystąpić taki ciąg \(\displaystyle{ a_{i}}\),
\(\displaystyle{ 1, 2, 3, 1, 2, 3...}\) - ten jako ciąg \(\displaystyle{ a_{i}}\) jest ok.

Już wiemy, że ciąg wynikowy \(\displaystyle{ n_{i}}\) jest okresowy najmarniej z takim samym okresem jak \(\displaystyle{ a_{i}}\) (post drugi Medea 2).

Muszę jednak wiedzieć czy w okresie podstawowym (najmniejszym) ciągu wynikowego \(\displaystyle{ n_{i}}\) wartości wyrazów także się nie powtarzają.
Awatar użytkownika
Medea 2
Użytkownik
Użytkownik
Posty: 2491
Rejestracja: 30 lis 2014, o 11:03
Płeć: Kobieta
Podziękował: 23 razy
Pomógł: 479 razy

Dwa ciągi liczbowe i ich okres

Post autor: Medea 2 »

Można ograniczyć poszukiwania do dzielników \(\displaystyle{ t}\). Spójrzmy jeszcze raz na moją równość, ale załóżmy teraz, że \(\displaystyle{ u}\) jest najmniejszym okresem dla \(\displaystyle{ n}\). Wtedy

\(\displaystyle{ n(i+u) = a(x+k(i+u)) = a(x+ki + ku) \stackrel{=}{?} a(x+ki) = n(i)}\).

Aby \(\displaystyle{ u}\) było minimalnym okresem, \(\displaystyle{ ku}\) musi być równe \(\displaystyle{ t}\) (lub jego wielokrotności).
Morfeo
Użytkownik
Użytkownik
Posty: 32
Rejestracja: 8 wrz 2015, o 19:21
Płeć: Mężczyzna
Lokalizacja: z daleka
Podziękował: 1 raz

Dwa ciągi liczbowe i ich okres

Post autor: Morfeo »

Medea 2 - dziękuję.

A mógłby może ktoś udowodnić (lub temu zaprzeczyć), że w okresie podstawowym (najmniejszym) ciągu wynikowego \(\displaystyle{ n_{i}}\) wartości wyrazów nie powtarzają się?

Wydaje mi się bardzo prawdopodobne, że jest to prawdą (ale potrzebuję pewności).
ODPOWIEDZ