🚀 go-pugleaf

waldek pisze:
> Są dwa rosnące ciągi arytmetyczne (w liczbach całkowitych):
> 
> A: a(n) = a(1) + (n-1) * ra
> B: b(m) = b(1) + (m-1) * rb
> 
> gdzie:
>  ra > 1
>  rb > ra
>  a(1) = b(1) (dla uproszczenia można przyjąć zero)
> 
> Próbuję wyprowadzić wzór na kolejne wyrazy ciągu C, takiego, który
> zawiera tylko i wyłącznie wszystkie wyrazy ciągów A i B.

1. a co to jest "wzór"?
2. czy chodzi Ci o ciąg C=a1,b1,a2,b2,a3,b3,...?

c(n)=\begin{cases}
   a((n+1)/2), n - nieparzyste\cr
   b(    n/2), n - parzyste\cr
\end{cases}

może tak być?


...

-- 
Adam Kolany, http://kolany.pl, gg. 17979733
===============================================================================
Media kłamią: w Abruzii nadal trzęsie się ziemia !
Szczegóły:
http://www.portaleabruzzo.com/navigazione/Speciale_Terremoto_6aprile2009_A.asp

Adam Kolany pisze:

 > 1. a co to jest "wzór"?

Coś w postaci:

c(i) = F(a(1), b(1), n, m, ra, rb)
lub
c(i) = F(n, m, ra, rb) dla a(1) = b(1) = 0


 > 2. czy chodzi Ci o ciąg C=a1,b1,a2,b2,a3,b3,...?
 >
 > c(n)=\begin{cases}
 >   a((n+1)/2), n - nieparzyste\cr
 >   b(    n/2), n - parzyste\cr
 > \end{cases}
 >
 > może tak być?
 >

Nie, gdyż tu tylko przeplatasz ze sobą wyrazy dwóch ciągów wyjściowych.

Może na przykładzie nieco innym, niż w poście inicjującym ten wątek 
będzie to lepiej widoczne:

A: 0, 2, 4, 6, 8, 10...
B: 0, 9, 18, 27...

C: 0, 2, 4, 6, 8, 9, 10...
    |  |  |  |  |  |  |
    A  A  A  A  A  |  A
    B              B

waldek

On Jul 20, 5:05 pm, waldek <xsw...@op.pl> sformułował
ciekawy(!) problem (który wyczuwam, ale moje dwa
rozwiąaania nie są w pełni zadawalające; podam też
ogólny obraz):

> Są dwa rosnące ciągi arytmetyczne (w liczbach całkowitych):
>
> A: a(n) = a(1) + (n-1) * ra
> B: b(m) = b(1) + (m-1) * rb
>
> gdzie:
>
>   ra > 1
>   rb > ra
>   a(1) = b(1) (dla uproszczenia można przyjąć zero)


Wolę założenie (indeksację):

    a(0) = b(0) = 0

(założenie ... = 0  nie traci ogólności, bo ogólne
do niego sprowadza się latwo przez przesunięcie).

> Próbuję wyprowadzić wzór na kolejne wyrazy ciągu C,
> takiego, który zawiera tylko i wyłącznie wszystkie wyrazy
> ciągów A i B.


Jak wyjaśniasz na przykładzie, chodzi Ci o ciąg,
którego zbiór wartości jest unią wartości danych
dwóch ciągów.

> Wyprowadziłem wzorek na sumę ciągu C dla wyrazów
> nie większych niż zadana liczba, co nie było zbyt trudne.

Fakt. Trudniejsza do wyliczenia jest
suma w duchu Twojego pytania,
mianowicie suma pierwszych n wyrazow.

> Ale jak zgrabnie wyliczyć same
> wyrazy ciągu C?
>
> Najprostszy z przykładów:

Waldku, to jest nietypowe (oryginalne)
i bardzo ciekawe pytanie. Mam niby dwa
rozwiązania, ale niezadawalające.

***
0. Redukcja
======================================

Najpierw (gdy  a(0) = b(0) = 0) zredukuję to zadanie
do szczególnego.  Niech  d := gcd(ra rb)
będzie największym wspólnym podzielnikiem
różnic ra rb, więc  rA := ra/d  oraz  rB := rb/d
są całkowite, przy czym:

    0 < rA < rB

    ra = d*rA
    rb = d*rB

Można założyć  rA > 1,  gdyż  rA=1  oznacza
przypadek trywialny, gdy ciąg o różnicy  ra
zawiera ciąg o różnicy  rb.

Zamiast ciągów  (n*ra)  oraz  (n*rb)
można rozpatrywać ciągi  (n*rA)  oraz  (n*rB).

Więc odtąd zakładam:

    gcd(ra rb)  =  1

***
***
1. Periodyczność
========================================

Zakładamy redukcję  gcd(ra rb) = 1. Rozwiązanie,
a raczej krok wstępny:

Pierwsze

            T  :=  ra+rb - 1

wyrazy  C(0) ... C(T-1)  jest łatwo (:-) wyliczyć.
Stąd wzor ogólny:

  C(n)  =  C(r)        gdzie  r :=  reszta(n T)

gdzie

    reszta(n T) = n - T * floor(n/T)

KONIEC ROZWIĄZANIA.

Rowiązanie to może być adekwatne dla małych
wartości  T.

***
***
2. Rekurencja
======================================

Niech  Sufit(x)  będzie najmniejszą liczbą całkowitą
taką, że

    x < Sufit(x).

(Zwróćcie uwagę na duże "S", oraz na **ostrą**
nierówność;  czyli   Sufit >/ sufit,  i nie zawsze
zachodzi równość).

Dla  n >/ 0  mamy:

    C(n+1)  =

        min( ra * Sufit(C(n)/ra),  rb * Sufit(C(n)/rb) )

To jest idealne rozwiązanie rekurencyjne,
ale chciało by się mieć wzór bezpośredni.

***
***

Bezpośrednie rozwiązanie, czyli wzór wprost
C(n)  ma za jądro ciąg rzeczywisty (nie całkowity)

    D(n)  :=  n * ra*rb / T

Ciąg  C(n)  oscyluje wokół ciągu  D(n).

Coś niecoś wiem w tym kierunku, ale
ostatecznego rozwiązania nie mam,
tylko dzielę się ideą.

***

Dziękuję Waldku za zadanie. Hilbert mówił,
że matematycy kochają dobre zadania
(problemy),

    Włodek

On Aug 29, 12:54 pm, "Wlodzimierz Holsztynski (Wlod)"
<sennaj...@gmail.com> wrote:
> [...]

Widzę, dopiero teraz, po ukazaniu się mojego postu,
że w podobnym duchu (choć niedokładnie to samo)
napisał tydzień temu Mirek. Mirek jest pesymistą,
a ja optymistą, gdy chodzi o rozwiązanie, które
byłoby w pełni przekonujące. Myślę, że w zadaniu
Waldka kryje się coś eleganckiego, choć niełatwego
do uchwycenia.

Przegapiłem Mirka, gdyż wcześniej wątek zapaskudziły
tępaki, mające się za filozofów i mędrcow (nie szkodzi,
skoro grupa jest niemoderowana; to znaczy - szkoda, ale
jest w porządku).

Włodek

Pisałem o redukcji do relatywnie pierwszych
rA rB (zastępujących  ra rb). Można w tym samym
duchu z miejsca zajmować się niezredukowanym
przypadkiem ogólnym (korzystając z redukcyjnych
rozważań; skupiłem się na zredukowanym przypadku,
by dalej unikać dodatkowych oznaczeń  rA  rB; a teraz
ich się już nie musicie obawiać, bo już jesteście
otrzaskani :-).

On Aug 29, 12:54 pm, "Wlodzimierz Holsztynski (Wlod)"
<sennaj...@gmail.com> wrote:

> Wolę założenie (indeksację):
>
>     a(0) = b(0) = 0
>
> ***
> 0. Redukcja
> ======================================
>
> Najpierw (gdy  a(0) = b(0) = 0) zredukuję to zadanie
> do szczególnego.  Niech  d := gcd(ra rb)
> będzie największym wspólnym podzielnikiem
> różnic ra rb, więc  rA := ra/d  oraz  rB := rb/d
> są całkowite, przy czym:
>
>     0 < rA < rB
>
>     ra = d*rA
>     rb = d*rB
>
> Można założyć  rA > 1,  gdyż  rA=1  oznacza
> przypadek trywialny, gdy ciąg o różnicy  ra
> zawiera ciąg o różnicy  rb.
>
> Zamiast ciągów  (n*ra)  oraz  (n*rb)
> można rozpatrywać ciągi  (n*rA)  oraz  (n*rB).
>
> Więc odtąd zakładam:
>
>     gcd(ra rb)  =  1
>
> ***
> ***
> 1. Periodyczność
> ========================================
>
> Zakładamy redukcję  gcd(ra rb) = 1. Rozwiązanie,
> a raczej krok wstępny:
>
> Pierwsze
>
>             T  :=  ra+rb - 1
>
> wyrazy  C(0) ... C(T-1)  jest łatwo (:-) wyliczyć.

Mogłem napisać ogólnie:

                T  :=  rA + rB - 1

Potem już wszystko jest tak samo.

> 2. Rekurencja
> ======================================
> Dla  n >/ 0  mamy:
>
>     C(n+1)  =
>
>         min( ra * Sufit(C(n)/ra),  rb * Sufit(C(n)/rb) )
>

To jest prawdą w dowolnym przypadku,
a nie tylko w zredukowanym.

Pozdrawiam,

    Włodek

On nie, 30 sie 2009 22:04:17 in article news:<d9d316c2-d36b-4148-ab0f-c183fde1fecd@y10g2000prg.googlegroups.com>
"Wlodzimierz Holsztynski (Wlod)" wrote:
>> ======================================
>> Dla  n >/ 0  mamy:
>>
>>     C(n+1)  =
>>
>>         min( ra * Sufit(C(n)/ra),  rb * Sufit(C(n)/rb) )
>>
> 
> To jest prawdą w dowolnym przypadku,
> a nie tylko w zredukowanym.

Moim skromnym zdaniem jest błąd, nie działa już dla n=0 ;)

Powinno być:

    min( ra * (1+floor(C(n)/ra)),  rb * (1+floor(C(n)/rb)) )

On Aug 31, 5:07 am, Mirek
<pisz_na.mi...@dionizos.zind.ikem.pwr.wroc.pl> wrote:
> On nie, 30 sie 2009 22:04:17 in article <news:d9d316c2-d36b-4148-ab0f-c183fde1fecd@y10g2000prg.googlegroups.com>
>
> "Wlodzimierz Holsztynski (Wlod)" wrote:
> >> ======================================
> >> Dla  n >/ 0  mamy:
>
> >>     C(n+1)  =
>
> >>         min( ra * Sufit(C(n)/ra),  rb * Sufit(C(n)/rb) )
>
> > To jest prawdą w dowolnym przypadku,
> > a nie tylko w zredukowanym.
>
> Moim skromnym zdaniem jest błąd, nie działa już dla n=0 ;)

Działa dla n=0 i dowolnego, coś Cię zaćmiło. Dla  n=0  mamy:

    C(n+1) = min( ra*Sufit(0),  rb*Sufit(0) ) = min( ra rb ) = ra

 - to co trzeba.

>
> Powinno być:
>
>     min( ra * (1+floor(C(n)/ra)),  rb * (1+floor(C(n)/rb)) )

To jest dokładnie to samo co napisałem, bowiem
z mojej definicji Sufitu (przez duże "S") mamy (jako
mikro-twierdzenie):

    Sufit(x)  =  1 + floor(x)

Użyłem notacji "Sufit", bo lepiej przemawia, bezpośrednio.

(Chyba nie nieporządnie czytałeś, po łebkach).

Pozdrawiam,

    Włodek

waldek pisze:
> Adam Kolany pisze:
> 
>  > 1. a co to jest "wzór"?
> 
> Coś w postaci:
> 
> c(i) = F(a(1), b(1), n, m, ra, rb)
> lub
> c(i) = F(n, m, ra, rb) dla a(1) = b(1) = 0
> 
> 
>  > 2. czy chodzi Ci o ciąg C=a1,b1,a2,b2,a3,b3,...?
>  >
>  > c(n)=\begin{cases}
>  >   a((n+1)/2), n - nieparzyste\cr
>  >   b(    n/2), n - parzyste\cr
>  > \end{cases}
>  >
>  > może tak być?
>  >
> 
> Nie, gdyż tu tylko przeplatasz ze sobą wyrazy dwóch ciągów wyjściowych.
> 
> Może na przykładzie nieco innym, niż w poście inicjującym ten wątek 
> będzie to lepiej widoczne:
> 
> A: 0, 2, 4, 6, 8, 10...
> B: 0, 9, 18, 27...
> 
> C: 0, 2, 4, 6, 8, 9, 10...
>    |  |  |  |  |  |  |
>    A  A  A  A  A  |  A
>    B              B
> 
> waldek

aha. czyli ma być bez powtórzeń.

to proszę.

c_0=min{a_0,b_0},
c_{n+1}=min ( (A\cup B)\setminus {c_0,\ldots,c_n} ), n=0,1,2,3,\ldots.

gdzie A={a_k:k=0,1,2,3,\ldots}, B={b_k:k=0,1,2,3,\ldots},

pozdrawiam,

 > Bezpośrednie rozwiązanie, czyli wzór wprost
 > C(n)  ma za jądro ciąg rzeczywisty (nie całkowity)
 >
 >    D(n)  :=  n * ra*rb / T
 >
 > Ciąg  C(n)  oscyluje wokół ciągu  D(n).

Też do tego doszedłem. Dla kilku szczególnych przypadków ciągów A i B 
wyznaczyłem również te oscylacje. Jednak nie potrafię tego uogólnić.

> Mirek jest pesymistą,
> a ja optymistą, gdy chodzi o rozwiązanie, które
> byłoby w pełni przekonujące. 

Wydaje się, że twój optymizm jest nieuzasadniony.

> Myślę, że w zadaniu
> Waldka kryje się coś eleganckiego, choć niełatwego
> do uchwycenia.

A tu z kolei intuicja Cię nie zawodzi:

1) Gdyby wzór dla dwóch ciągów można było wyprowadzić w "dostatecznie 
eleganckiej" postaci

oraz

2) dzięki owej elegancji *dodatkowo* uogólnić na dowolną ilość ciągów 
arytmetycznych o wyrazach początkowych równych zeru i różnicach kolejno: 
2, 3, 4, 5, 6...N (lub prościej: 2, 3, 5, 7, 11, 13...N)

to uzyskalibyśmy formułę do wyznaczania kolejnych liczb złożonych od N+1 
do N^2. Stąd już tylko rzut beretem do magicznego wzoru na n-tą liczbę 
pierwszą. No, może nie do końca beretem, ale prawie...
Prawdę mówiąc, zakładałem ten wątek spodziewając się, że dla dwóch 
ciągów rozwiązanie jest znane, a problem istnieje z jego rozszerzeniem 
na większą ilość ciągów. Teraz jednak myślę, że gdyby już dla dwóch 
ciągów rozwiązanie istniało, to hipotezy Riemanna i Goldbacha byłyby od 
dawna twierdzeniami. :-)

waldek