jak sprawdzić punkty wspólne dwóch ciągów

[Rebus27]

Mam takie dwa ciągi i chciałbym wyliczyć szybko ile mają w danym przedziale punktów wspólnych i jakie te punkty są:
Pierwszy ciąg \(\displaystyle{ x+y}\) wynik to pierwszy wyraz ciągu następny to wynik + y powiększony o 8 i znowu w następnym kroku wynik + y powiększony o 8 czyli np \(\displaystyle{ x=1, y=1}\) to tak \(\displaystyle{ 2,11,28,53...}\)
A drugi ciąg jest trochę inny i zawsze taki sam \(\displaystyle{ 0,8,24,48,80...}\) albo zaczynający się nie od 0 tylko od 4
czyli: \(\displaystyle{ 0,0+(1 \cdot 8)=8,8+(2 \cdot 8)=24,24+(3 \cdot 8)=48...}\)
w zasadzie potrzebuję jakiegokolwiek wspólnego punktu w danym przedziale
Czy istnieje jakaś metoda żeby to szybciej wyliczyć niż generować ciągi i porównywać ich kolejne wyrazy?

[kerajs]

Piszesz ten post już trzeci raz, a wciąż mętnie opisujesz powyższe ciągi .

Chyba chodzi ci o ciągi rekurencyjne:
\(\displaystyle{ a _{1} =x \wedge a _{n}=a _{n-1}+y+(n-1) \cdot 8}\)
\(\displaystyle{ b _{1} =t \wedge b _{n}=b _{n-1}+(n-1) \cdot 8}\)

Nie rozumiem dlaczego szukasz ,,łatwiejszego "sposobu. Przecież algorytm wyliczania wszystkich wyrazów obu ciągów w konkretnym przedziale i znalezienia powtarzających się liczb jest o wiele prostszy niż programowanie ,,łatwiejszego" sposobu, o ile taki by istniał.
A jeśli przedział w którym mogą być wspólne wyrazy obu ciągów jest duży to podziel go na mniejsze. Dla każdego dokonuj sprawdzenia i opróżniaj rejestry przechowujące wyliczone, zbędne już dane.

[Rebus27]

No a gdyby istniała metoda która zamienia te dwa ciągi na jakieś równania nie wiem może nawet kwadratowe nie znam się na tyle po czym rozwiązanie od razu dałoby punkt wspólny to by nie było szybciej? Normalnie nic nie trzeba zapisywać po prostu dwie zmienne które są porównywane jeżeli wartość pierwszego ciągu jest większa to przejdź do następnego wyrazu ciągu drugiego i porównaj znowu jeśli mniejsza to przejdź do następnego wyrazu ciągu pierwszego... ale gdy moje przedziały będą może od 0 do 1000 cyfrowej liczby to ile ja mam czekać? Gdybym mieścił się w long longu to bym nie narzekał.

[yorgin]

W innym temacie napisałem Ci, jak wygląda rozwiązanie rekurencji, z którą masz problem. Wzór ogólny to wielomian stopnia drugiego ze względu na \(\displaystyle{ n}\). Dwa wielomiany drugiego stopnia albo są równe wszędzie, albo mają jeden punkt wspólny, albo dwa. Pierwszy wariant wynika wprost z równości obu wielomianów. Drugi i trzeci to rozwiązanie równania kwadratowego ze względu na \(\displaystyle{ n}\) - to jest łatwe do zaimplementowania oraz wyliczenia. Poza tym przy takich ciągach oraz stosunkowo niskich wartościach początkowych \(\displaystyle{ x}\) oraz \(\displaystyle{ y}\) nie będziesz długo czekał na albo równe, ale brak równości. Wystarczy trywialna analiza na poziomie szkoły średniej, by to stwierdzić.

[Rebus27]

Ok to dobrze. A jeszcze jedno przy stosunkowo niskich wartościach \(\displaystyle{ x i y}\) ? A co gdy będą tak liczbami wielkości 100-cyfrowymi albo większe komputer mam nadzieję że nie będzie miał problemu. Kurcze muszę sobie poprzypominać wielomiany na co dzień się tego do programowania nie stosuje także dobrze że się da ale dziś mam korepetycje na gg więc jakiś tam matematyk mi to wyjaśni krok po kroku co ja muszę zrobić nie będę wam już zawracał głowy

[kerajs]

No to może dokończę, choć Yorgin już ci to napisał już dwa razy .

Powyższe ciągi mają wzory ogólne
\(\displaystyle{ a _{n} =x+(n-1) \cdot y+ \frac{(n-1) \cdot n}{2} \cdot 8}\)
\(\displaystyle{ b _{n} =t+ \frac{(n-1) \cdot n}{2} \cdot 8}\)
(lub takie jak podano ci w poprzednim poście, którego niestety wcześniej nie przeczytałem do końca )
Po podstawieniu za x,y,t odpowiednio 1,1,0 masz
\(\displaystyle{ a _{n} =4 \cdot n ^{2}-3 \cdot n}\)
\(\displaystyle{ b _{n} =4 \cdot n ^{2}-4 \cdot n}\)

Ineresuje cię aby \(\displaystyle{ a _{p}=b _{q}}\)
co daje równanie \(\displaystyle{ 4 \cdot p ^{2}-3 \cdot p=4 \cdot q ^{2}-4 \cdot q}\)
(dla innych x, y t będzie ono miało postać
\(\displaystyle{ x+(p-1) \cdot y+4 \cdot p ^{2}-4 \cdot p=t+4 \cdot q ^{2}-4 \cdot q}\) )


Równanie \(\displaystyle{ 4 \cdot p ^{2}-3 \cdot p=4 \cdot q ^{2}-4 \cdot q}\) ma dwie niewiadome więc jedną potraktuj jak parametr. Dla niewiadomej q masz równanie kwadratowe
\(\displaystyle{ q ^{2}-q+(0.75 \cdot p-p ^{2})=0}\)
które zwyczajnie rozwiązujesz, lub raczej piszesz program który sprawdza dla jakich naturalnych p otrzymane q jest naturalne.

[Rebus27]

I to jest odpowiedź, trzeba było tak od razu. Nie przypomina mi się, żeby mi ktoś coś takiego pisał. Albo ja nie umiem korzystać z tego forum... Mniejsza o to, ale i tak jutro mam korepetycje online z matematyki i się wszystko wyjaśni. Dzięki kerajs