> Czy istnieje JAWNY WZÓR na n-tą liczbę ? Nie wiem, nie znam się. Wy się znacie ? A może nie
>wiadomo ?

Czemu miałby nie istnieć? Liczba elementów na każdej linii jest kolejną liczbą naturalną. Czyli, dla dowolnego n, odejmujemy od tego największą liczbę trójkątną mniejszą od n. Numer tej liczby trójkątnej wyznacza nam na której linii jesteśmy, wynik odejmowania to pozycja na linii. Koniec liczenia.

Czy może znowu jest tutaj jakiś niby to podchwytliwy haczyk którego nie widzę?

>> Czy istnieje JAWNY WZÓR na n-tą liczbę ? Nie wiem, nie znam się. Wy się znacie ? A może nie
>>wiadomo ?
>Czemu miałby nie istnieć?

No przecież dla 'niektórych' ciągów określonych rekurencyjnie nie znamy ogólnego wzoru na n-ty wyraz (i nigdy nie poznamy wg tw. Goedla, tak?). Tutaj mamy do czynienia z graficznym przedstawieniem rozumowania. Jak w takim razie obliczyć np. 44 wyraz nie 'na palcach' ? Oblicz go !

---

"Największy błąd popełnia ten, kto sądząc, że może zrobić niewiele, nie robi nic"

> Oblicz go !

Przecież napisałem algorytm na to. Po co mam liczyć? Zresztą, taki sam zygzak jest stosowany w grafice komputerowej - chociażby popularny algorytm JPEG z tego korzysta.

>> Czy istnieje JAWNY WZÓR na n-tą liczbę ? Nie wiem, nie znam się. Wy się znacie ? A może nie
>>wiadomo ?
>Czemu miałby nie istnieć? Liczba elementów na każdej linii jest kolejną liczbą naturalną. Czyli, dla dowolnego n, odejmujemy od tego największą liczbę trójkątną mniejszą od n. Numer tej liczby trójkątnej wyznacza nam na której linii jesteśmy, wynik odejmowania to pozycja na linii. Koniec liczenia.
>Czy może znowu jest tutaj jakiś niby to podchwytliwy haczyk którego nie widzę?

Owszem, istnieje taki haczyk. Aby udowadniać równoliczność dwóch zbiorów, konieczna jest konstrukcja bijekcji, która musi być między innymi różnowartościowa. Problem polega na tym, że przy konstruowaniu macierzy w zadany sposób, występują powtórzenia: 1/1 i 2/2 to ta sama liczba wymierna. Nie usuwając tych powtórzeń z szeregu, udowadniamy, co najwyżej, że moc zbioru liczb wymiernych jest mniejsza lub równa mocy zbioru liczb naturalnych, a nie równa. Aby wykazać równoliczność konieczne jest usuwanie wszystkich elementów, dla których NWD(p,q) jest większe od 1.

Nie sprawdzałem tego, ale w ogólności, określenie wzoru na n-ty wyraz, który będzie uwzględniał odrzucanie "powtórzeń" może być nietrywialne, jeżeli w ogóle możliwe.

>Nie sprawdzałem tego, ale w ogólności, określenie wzoru na n-ty wyraz, który będzie uwzględniał odrzucanie "powtórzeń" może być nietrywialne, jeżeli w ogóle możliwe.

No właśnie o to mi chodzi Pozdrawiam.

---

"Największy błąd popełnia ten, kto sądząc, że może zrobić niewiele, nie robi nic"

>>Nie sprawdzałem tego, ale w ogólności, określenie wzoru na n-ty wyraz, który będzie uwzględniał odrzucanie "powtórzeń" może być nietrywialne, jeżeli w ogóle możliwe.
>No właśnie o to mi chodzi Pozdrawiam.

Nigdzie nie pisałeś o odrzucaniu powtórzeń w poście otwierającym wątek...

>?! Tzn. Czy istnieje JAWNY WZÓR na n-tą liczbę ? Nie wiem, nie znam się. Wy się znacie ? A może nie
>wiadomo ?

Wzór podaje angielska wikipedia pod hasłem "pairing function" (po polsku to się nazywa funkcja pary). Podany tam wzór pasuje wprawdzie do nieco innego sposobu zbierania liczb po przekątnych niż ten podany przez Pana, ale to mało istotny detal. Wzór z wikipedii jest dla następującego sposobu:
0 --> (0, 0)
1 --> (1, 0)
2 --> (0, 1)
3 --> (2, 0) (tu pierwsza różnica w porównaniu z Pana sposobem)
itd.
Czyli: zaczynamy od lewego górnego rogu (pierwsza przekątna); potem zakreślamy drugą przekątną idącą od drugiego pola w górnym rzędzie; potem nie robimy zygzaka (jak u Pana) tylko zakreślamy trzecią przekątną zaczynając od trzeciego pola w górnym rzędzie, itd.

>No przecież dla 'niektórych' ciągów określonych rekurencyjnie nie znamy ogólnego wzoru na n-ty wyraz (i nigdy nie poznamy wg tw. Goedla, tak?)

Nie rozumiem. Ciąg rekurencyjny to z definicji właśnie taki ciąg, dla którego istnieje ogólny algorytm określania n-tego wyrazu. Co więcej, ten ogólny algorytm zawsze potrafimy opisać formułą arytmetyczną niskiego stopnia złożoności (mówi o tym tzw. twierdzenie o reprezentowalności). Tym czego nie dostaniemy w przypadku niektórych ciągów rekurencyjnych jest algorytm sprawdzający czy dana liczba k (dowolna) kiedyś w tym ciągu się pojawi. Ale to jest trochę co innego niż to, co Pan pisze.

---

But little they cared for the Native Press
The worn white soldiers in Khaki dress

>Nie rozumiem. Ciąg rekurencyjny to z definicji właśnie taki ciąg, dla którego istnieje ogólny algorytm określania n-tego wyrazu.

A np. ciąg Fibonacciego ? Znamy jawny wzór na n-ty wyraz ?
Akurat znamy Wzór Bineta - ale nie było to takie oczywiste, że uda się go znaleźć lub, że on w ogóle istnieje. W (nieskończenie)wielu przypadkach takiego wzoru znaleźć nie umiemy lub on w ogóle może nie istnieć lub inne cuda wynikające z tw. Goedla.

---

"Największy błąd popełnia ten, kto sądząc, że może zrobić niewiele, nie robi nic"

>A np. ciąg Fibonacciego ? Znamy jawny wzór na n-ty wyraz ?
>Akurat znamy Wzór Bineta - ale nie było to takie oczywiste, że uda się go znaleźć lub, że on w ogóle istnieje. W (nieskończenie)wielu przypadkach takiego wzoru znaleźć nie umiemy lub on w ogóle może nie istnieć lub inne cuda wynikające z tw. Goedla.

Ma Pan rację, jest tu jakieś zagadnienie. Obecnie podaje się często przykład funkcji Ackermanna jako czegoś zadanego tylko przez równania rekurencyjne, a nie jawny wzór. Mógłby Pan jednak wyjaśnić, w jaki sposób nieistnienie takiego wzoru miałoby wynikać z tw. Goedla (szkic argumentu albo link)?

---

But little they cared for the Native Press
The worn white soldiers in Khaki dress

>Mógłby Pan jednak wyjaśnić, w jaki sposób nieistnienie takiego wzoru miałoby wynikać z tw. Goedla (szkic argumentu albo link)?

Z tw. Goedla i pochodnych tw. dotyczących podstaw matematyki mogłoby np. wynikać, że istnienie jawnego wzoru na n-ty wyraz jakiegoś 'konkretnego' ciągu jest niedowodliwe, a w "skończonej praktyce", że takiego wzoru nie ma.

~ coś a'la to co Cohen pokazał dla hipotezy Continuum (a'la znaczy 'w tym klimacie' bo analogii tu nie ma )

---

"Największy błąd popełnia ten, kto sądząc, że może zrobić niewiele, nie robi nic"

Twierdzenie Goedla nie ma nic do wzorów rekurencyjnych. Chyba Pan nie za bardzo rozumie tw. Goedla. Kiedys na ten temat pisalem. Co do rekurencji, to ZAWSZE ISTNIEJE FUNKCJA, ktora ja rozwiązuje. To jest twierdzenie z podstaw matematyki - teorii mnogości. To nie jest trywialne twierdzenie, a nawet bardzo trudne, i dlatego nawet studentów matematyki się do niego nie wprowadza. Co więcej, dowodzi się, że każda rekurencja określona na liczbach porządkowych (w szczególności są nimi liczby naturalne), jest DOBRZE OKREŚLONA, co oznacza, że istnieje dokładnie jedna funkcja, która ją rozwiązuje. Polecam książki z teorii mnogości, ale poważne, a nie podręczniki szkolne.

---

Lepiej jest z mądrym zgubić, niż z głupim znaleźć.

Zatem istnieje wzór na liczby pierwsze? (Jestem ciekawy! Liczby pierwsze to graal kryptologii.)

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

>Zatem istnieje wzór na liczby pierwsze? (Jestem ciekawy! Liczby pierwsze to graal kryptologii.)

A to liczby pierwsze są określone rekurencyjnie?

>>Zatem istnieje wzór na liczby pierwsze? (Jestem ciekawy! Liczby pierwsze to graal kryptologii.)
>A to liczby pierwsze są określone rekurencyjnie?
Tak. Każda następna liczba pierwsza jest większa od poprzeniej oraz zależy od poprzednich.

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

>>>Zatem istnieje wzór na liczby pierwsze? (Jestem ciekawy! Liczby pierwsze to graal kryptologii.)
>>A to liczby pierwsze są określone rekurencyjnie?
>Tak. Każda następna liczba pierwsza jest większa od poprzeniej oraz zależy od poprzednich.

Phi. To ma być wzór rekurencyjny? To można powiedzieć o dowolnych liczbach naturalnych, które ułożone są w porządku rosnącym.

>Phi. To ma być wzór rekurencyjny? To można powiedzieć o dowolnych liczbach naturalnych, które ułożone są w porządku rosnącym.
Nie dowolnych. Musi być jednoznaczny sposób, w jaki następujące liczby wynikają z poprzedzających.
Najprostszą rekurencją na liczbach naturalnych jest: n0 = 0, nk = n(k-1) + 1;

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

>>Phi. To ma być wzór rekurencyjny? To można powiedzieć o dowolnych liczbach naturalnych, które ułożone są w porządku rosnącym.
>Nie dowolnych. Musi być jednoznaczny sposób, w jaki następujące liczby wynikają z poprzedzających.
>Najprostszą rekurencją na liczbach naturalnych jest: n0 = 0, nk = n(k-1) + 1;

I uważasz, że taki wzór istnieje dla liczb pierwszych? Chyba tylko i wyłącznie na zasadzie p[n]=p[n-1]+a[n], gdzie a[n] = p[n] - p[n-1]

Późna pora, nie bardzo rozumiem, czego ode mnie chcesz?
Jest jasne, że znając wszystkie poprzedzające liczby pierwsze da się wyznaczyć następną liczbę pierwszą. Robi się to jednak od "tyłka strony" - bierze liczbę i sprawdza, czy się dzieli przez liczby pierwsze. Pytanie, czy da się to zrobić od "normalnej strony" - wychodząc od znanych nam już liczb pierwszych.

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

Obawiam się, że podajesz algorytm wyznaczania następnej, a nie wzór rekurencyjny na następną. To dwie różne rzeczy.

---

Lepiej jest z mądrym zgubić, niż z głupim znaleźć.

>Obawiam się, że podajesz algorytm wyznaczania następnej, a nie wzór rekurencyjny na następną. To dwie różne rzeczy.
Tak, podałem algorytm. Wiem, że to dwie różne rzeczy.
Nie wiedziałem, o co 'stilgarowi' chodzi. Przecież to ja pytałem Ciebie, czy istnieje wzór, a on zaczął pytać mnie, czy myślę, że taki wzór istnieje.

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

Nie zrozumiał Pan. Twierdzenie mówi, że ISTNIEJE dokładnie jedna FUNKCJA, a nie że istnieje wzór analityczny. To zupełnie dwie różne kwestie.

---

Lepiej jest z mądrym zgubić, niż z głupim znaleźć.

Teraz ja się pogubiłem. Jest wzór pozwalający jednoznacznie przejść z ostatniej liczby pierwszej (do jakiej doszliśmy) na następną? Czy nie ma?
Nie chodzi mi o to, bym go dostał napisanego, tylko pytam, czy jest.

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

>Teraz ja się pogubiłem. Jest wzór pozwalający jednoznacznie przejść z ostatniej liczby pierwszej (do jakiej doszliśmy) na następną? Czy nie ma?

Póki co, nie ma. Jak na razie jedyną pewną metodą pozostaje sławne sito. No i częściowe wzory, dla pewnych zakresów...

>Teraz ja się pogubiłem. Jest wzór pozwalający jednoznacznie przejść z ostatniej liczby pierwszej (do jakiej doszliśmy) na następną? Czy nie ma?
>Nie chodzi mi o to, bym go dostał napisanego, tylko pytam, czy jest.

Czy jest... Tego nikt nie wie. Może tak, a może nie. Proszę jednak zauważyć przy okazji, że istnienie funkcji, a istnienie wzoru analitycznego - jak wspomniałem - to dwie kompletnie różne sprawy.

---

Lepiej jest z mądrym zgubić, niż z głupim znaleźć.

Czyli odpowiedź brzmi: nie wiadomo.
Dzięki.

Myślałem, że twierdzenie o istnieniu funkcji ujednoznacznia istnienie/nieistnienie wzoru.

Pozdrawiam

---

Ginosaji - nowa ikona popkultury.
Z łyżeczką!

>Twierdzenie Goedla nie ma nic do wzorów rekurencyjnych. Chyba Pan nie za bardzo rozumie tw. Goedla. Kiedys na ten temat pisalem. Co do rekurencji, to ZAWSZE ISTNIEJE FUNKCJA, ktora ja rozwiązuje. To jest twierdzenie z podstaw matematyki - teorii mnogości. To nie jest trywialne twierdzenie, a nawet bardzo trudne, i dlatego nawet studentów matematyki się do niego nie wprowadza. Co więcej, dowodzi się, że każda rekurencja określona na liczbach porządkowych (w szczególności są nimi liczby naturalne), jest DOBRZE OKREŚLONA, co oznacza, że istnieje dokładnie jedna funkcja, która ją rozwiązuje. Polecam książki z teorii mnogości, ale poważne, a nie podręczniki szkolne.

darlove, jest oczywiście tak jak Pan pisze, ale jemu nie chodzi o istnienie funkcji spełniającej rekurencyjne warunki, tylko o klasę wyrażeń, przez które takie funkcje są wyznaczane. O ile dobrze rozumiem, on pyta o to, jak przekształcać rekurencyjne równania na "jawne wzory" - takie, w których nie odwołujemy się do wcześniejszego przebiegu funkcji, lecz korzystamy z jej argumentów (tu porównanie rekurencyjnej charakterystyki ciągu Fibonacciego ze wzorem Bineta, który nie zawiera rekursji). Techniki dokonywania takich przekształceń nie są ani trywialne, ani (z tego co się orientuję) uniwersalne. Chyba że się mylę i jednak są jakieś uniwersalne? Też się chętnie dowiem.

---

But little they cared for the Native Press
The worn white soldiers in Khaki dress

Nie ma uniwersalnych zasad. Wszystko, co wiadomo o rozwiązywaniu rekurencji, to doświadczenia matematyków gromadzone wiekami, ale daje się przedstawić rekurencje w sposób jawny tylko w określonych przypadkach. Ogólnego wzoru lub algorytmu nie ma (i zapewne być nie może).

Na temat matematyki komputerowej, bo pod to podpada teoria rekurencji i funkcji integralnych, jest cudna książka napisana między innymi przez Donalda Knutha (komputerowcy wiedzą, kto zacz) pt. Matematyka dyskretna. Polecam.

>daje się przedstawić rekurencje w sposób jawny tylko w określonych przypadkach.

Do wszystkich: będę wdzięczny za namiar na tekst, w którym jest pokazany dowód czegoś takiego. Obiecuję w zamian punkta

---

But little they cared for the Native Press
The worn white soldiers in Khaki dress

Namiar masz w moim poście. Nie zauważyłeś, że podałem literaturę? Sprawa jest analogiczna do np. rozwiązywania równań różniczkowych. Istnieją takie, że tylko metodami numerycznymi się je da "rozwalić".

>Namiar masz w moim poście. Nie zauważyłeś, że podałem literaturę? Sprawa jest analogiczna do np. rozwiązywania równań różniczkowych. Istnieją takie, że tylko metodami numerycznymi się je da "rozwalić".
>
Spoko. Myślałem, że podajesz to jako ogólne źródło. Sprawdzę i jak jest, wiszę punkta

---

But little they cared for the Native Press
The worn white soldiers in Khaki dress

>Nie ma uniwersalnych zasad. Wszystko, co wiadomo o rozwiązywaniu rekurencji, to doświadczenia matematyków gromadzone wiekami, ale daje się przedstawić rekurencje w sposób jawny tylko w określonych przypadkach. Ogólnego wzoru lub algorytmu nie ma (i zapewne być nie może).

Na liniowe wzory rekurencyjne są ogólne metody; całkiem podobne do metod rozw. liniowych równań różniczkowych.

Na nieliniowe metody nie ma i nigdy nie będzie.

>Na nieliniowe metody nie ma i nigdy nie będzie.

Złagodźmy trochę to zdanie, bo nie mówi ono całej prawdy: istnieją metody rozwiązywania takich rzeczy, czyli nieliniowych rekurencji, ale tylko w bardzo dobrze określonych formach. To tak samo, jak z równaniami różniczkowymi: istnieją metody rozwiązywania równań nieliniowych, ale równania muszą być bardzo specyficznej postaci. Jeśli mi ktoś nie wierzy (to jego problem), to może sięgnąć do Wiki. Na przykład.

---

Lepiej jest z mądrym zgubić, niż z głupim znaleźć.