Tetracja i nieskończona wieża wykładnicza

Tetracja - definicja

Tetracja (wieża wykładnicza, super-potęgowanie, iterowane potęgowanie, 4 hiper-operator)

Tetracja to działanie dwuargumentowe definiowane jako wielokrotne potęgowanie elementu przez siebie.

Definicja: dla dowolnej liczby rzeczywistej a>0 i nieujemnej liczby całkowitej n\geq 0 tetrację n liczby a definiujemy jako:

{^{n}a}=\begin{cases}1&\text{dla}\quad n=0\\a&\text{dla}\quad n=1\\ \underbrace{a^{a^{\cdots^{a}}}}_{n}&\text{dla}\quad n>1\end{cases}

Przykłady

{^{3}2}=2^{2^2}=2^{(2^2)}=2^4=16

{^{4}2}=2^{2^{2^2}}=2^{(2^{(2^2)})}=2^{(2^{4})}=2^{16}=65536

{^{3}3}=3^{3^3}=3^{(3^3)}=3^{27}=7625597484987

{^{4}3}=3^{3^{3^3}}=3^{(3^{(3^3)})}=3^{(3^{27})}=3^{7625597484987}=\ldots liczba składająca się z 3638334640025 cyfr 🙂

Tetrację można wykorzystać do zapisu naprawdę dużych liczb, co dobrze obrazuje przykład {^{4}3}. Tetrację wygodnie jest również definiować w postaci rekurencyjnej.

Definicja rekurencyjna: dla dowolnej liczby rzeczywistej a>0 i nieujemnej liczby całkowitej n\geq 0 tetrację n liczby a definiujemy jako:

{^{n}a}=\begin{cases}1&\text{dla}\quad n=0\\a^{{^{n-1}a}}&\text{dla}\quad n\geq 1\end{cases}

Funkcja f(x)=x^x i związek tetracji z liczbą e

Funkcja x^x

f(x)=x^x to podstawowy przykład funkcji na bazie tetracji.

Własności f(x)=x^x

  • f(x)=x^x jest określona na dodatnich liczbach rzeczywistych
  • 0^0 jest symbolem nieokreślonym, ale x^x\to 1 gdy x\to 0^+
  • f(x)=x^x posiada minimum e^{-\frac{1}{e}} w punkcie x=\frac{1}{e}
  • f(x)=x^x maleje w przedziale x\in(0, \frac{1}{e}), rośnie w przedziale x\in(\frac{1}{e},+\infty)
  • f^\prime(x)=x^x\big(\ln x+1\big)

Pochodna f(x)=x^x

Aby policzyć pochodną x^x wystarczy zastosować drobny trick na bazie własności logarytmu.

f(x)=x^x

x>0 oraz f(x)>0

\ln f(x)=\ln x^x=x\ln x

\Big(\ln f(x)\Big)^\prime=\Big(x\ln x\Big)^\prime

\frac{1}{f(x)}f^\prime(x)=x^\prime\ln x + x\Big(\ln x\Big)^\prime=\ln x + 1

f^\prime(x)=(x^x)^\prime

f^\prime(x)=f(x)\Big(\ln x + 1\Big)=x^x\Big(\ln x + 1\Big)

Bazując na rekurencyjnej definicji tetracji, korzystając z powyższego tricku, można wyznaczyć ogólną rekurencyjną formułę na pochodną tetracji n liczby x. Mając pochodną z łatwością wykazujemy większość podanych własności.

Nieskończona wieża wykładnicza i jeszcze silniejszy związek tetracji z liczbą e

{\Huge x^{x^{x^{x^{x^{\cdots}}}}}=?}

Problem zbieżności ciągu tetracji został rozwiązany już w XVIII wieku, a dokonał tego Leonhard Euler 🙂 Rozważmy granicę

\lim_{n\to\infty}{^{n}x}

zadając pytanie "dla jakich x>0 istnieje powyższa granica?"

Na potrzeby rozważań załóżmy, że taka granica istnieje i wynosi

\lim_{n\to\infty}{^{n}x}=y

Bazując na rekurencyjnej definicji tetracji otrzymujemy

y=\lim_{n\to\infty}{^{n}x}=\lim_{n\to\infty}x^{^{n-1}x}=

=x^{\lim_{n\to\infty}{^{n-1}x}}=x^y

Zatem, warunkiem koniecznym dla zbieżności ciągu tetracji jest

y=x^y

gdzie

\lim_{n\to\infty}{^{n}x}=y

Przekształcając y=x^y

y^{\frac{1}{y}}=(x^y)^{\frac{1}{y}}

otrzymujemy

x=y^\frac{1}{y}

Uwaga: nie jest to warunek dostateczny!

Twierdzenie Eulera o zbieżności ciągu tetracji: y=\lim_{n\to\infty}{^{n}x} istnieje i jest skończona wyłącznie jeśli x\in\Big[e^{-e},e^\frac{1}{e}\Big]. Zachodzi wtedy

y\in\Big[\frac{1}{e},e\Big]

dla

x\in\Big[e^{-e},e^\frac{1}{e}\Big]

Dowód powyższego twierdzenia wykracza poza objętość tego artukułu, zainteresowanych zapraszam do publikacji R. Arthur Knoebel , Exponentials Reiterated.

Tetracja - zbieżność

Na koniec niesamowita estetyka, która ujawnia się w nieskończonej wieży wykładniczej

W przedziale y\in\Big[\frac{1}{e},e\Big] leżą tylko dwie liczby całkowite: 1 i 2.

y=1 to x=1

y=2 to x=2^\frac{1}{2}=\sqrt{2}

Piękne - nieskończona tetracja \sqrt{2} daje w wyniku 2 🙂

Wieża potęgowa - Tetracja

Pozdrowienia,

Mariusz Gromada

 

 

 

Ukryty wymiar liczb - czyli liczby zespolone (część 1)

Liczby naturalne \mathbb{N}

Podział liczb - #1

Początki matematyki to liczby naturalne \mathbb{N} = \{1,2,3,\ldots\}, czyli narzędzie służące do opisu liczności (np. trzy elementy) lub do podawania kolejności (np. trzecia osoba). Z biegiem czasu do liczb wprowadzono pierwsze działania - dodawanie i mnożenie. Z łatwością można wykazać, że liczby naturalne są zamknięte ze względu na dodawanie i mnożenie - jednak nim przejdziemy dalej - wyjaśnię w kilku słowach co to tak naprawdę oznacza.

Zamkniętość zbioru ze względu na działanie

Rozważmy dowolny zbiór A oraz dwuargumentowe działanie a*b określone na elementach a, b \in A.

Mówimy, że zbiór A jest zamknięty ze względu na działanie * jeśli dla dowolnych a, b \in A istnieje c \in A, że c=a*b.

Inaczej mówiąc, zbiór jest zamknięty ze względu na dane działanie jeśli wszystkie możliwe wyniki wskazanego działania (na elementach rozważanego zbioru) są również elementami tego zbioru. W analogi do dodawania i mnożenia liczb naturalnych możemy stwierdzić, że suma dwóch liczb naturalnych jest liczbą naturalną, a w konsekwencji mnożenie dwóch liczb naturalnych daje także wynik w liczbach naturalnych.

\Big(\mathbb{N}, +, \times\Big)

Wraz z rozwojem matematyki wprowadzano kolejne działania, które ujawniły "niekompletność" zbioru liczb naturalnych.

Liczby całkowite \mathbb{Z} jako "domknięcie" odejmowania "-"

Podział liczb - #2

Wprowadzenie odejmowania pokazało, że liczby naturalne nie są zamknięte ze względu na to działanie. Dla wielu liczb naturalnych wynik odejmowania jest liczbą naturalną, jednak istnieje równie wiele przykładów uzasadniających wniosek przeciwny, np.:

2-5 = -3 \notin \mathbb{N}

Uzupełniając liczby naturalne o liczby do nich przeciwne oraz 0 otrzymujemy liczby całkowite \mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\} zamknięte również ze względu na odejmowanie.

\Big(\mathbb{Z}, +, \times,-\Big)

Liczby wymierne \mathbb{Q} jako "domknięcie" dzielenia \frac{\cdot}{\cdot}

Podział liczb - #3

Liczby wymierne wyrażając proporcję (stosunek) pomiędzy wielkościami powstają z ilorazu dwóch liczb całkowitych.

Każdą liczbę wymierną można zapisać jako ułamek, tzn. \mathbb{Q}=\Big\{\frac{m}{n}:m,n\in\mathbb{Z},n\neq 0\Big\} gdzie m, n są liczbami całkowitymi, a n jest różne od 0.

I choć dla części liczb naturalnych ich iloraz jest również liczbą naturalną (np. 10 / 2 = 5), to istnieje równie wiele przypadków sytuacji odwrotnej, np.

\frac{1}{5}\notin\mathbb{Z}

Liczby wymierne są zamknięte ze względu na iloraz (z pominięciem 0 - gdyż dzielenie przez 0 nie jest określone).

\Big(\mathbb{Q}, +, \times,-, \frac{\cdot}{\cdot}\Big)

Liczby algebraiczne jako "częściowe domknięcie" pierwiastkowania \sqrt{\cdot} i potęgowania {m}^{n}.

Podział liczb - #4

Już Pitagoras potrafił wykazać że długości przekątnej jednostkowego kwadratu nie da się wyrazić jako stosunku ówcześnie znanych liczb. Z twierdzenia Pitagorasa łatwo zapisujemy

x^2=1^2+1^2

x^2=2

x=+/-\sqrt{2}\notin\mathbb{Q}

Pierwiastek z liczby 2 nie jest liczbą wymierną, podobnie jak i \sqrt{3}\sqrt{5}, ... Zapiszmy nieco ogólniej

x^2-2=0

Zatem pierwiastek z liczby 2 jest zerem wielomianu (pierwiastkiem wielomianu) o wymiernych współczynnikach.

Liczby algebraiczne, zdefiniowane jako rozwiązania wielomianów o wymiernych współczynnikach, są pierwszym etapem "domknięcia" liczb wymiernych.

Liczby rzeczywiste \mathbb{R} jako granice ciągów liczb wymiernych.

Podział liczb - #5

Liczby wymierne (nawet rozszerzone o liczby algebraiczne) nie są zupełne.

Zbiór nazywamy zupełnym jeśli w zbiorze istnieje granica każdego ciągu spełniającego warunek Cauchy'ego.

Wykres ciągu Cauchy’ego Wykres ciągu Cauchy’ego - źródło wikipedia.org

Mówimy, że ciąg spełnia warunek Cauchy'ego, jeśli dla ustalonej dowolnie małej liczby, pomijając skończoną liczbę elementów ciągu, "odległość" pomiędzy pozostałymi dowolnymi dwoma elementami ciągu nie przekracza ustalonej wartości.

Dobrym i bardzo znanym przykładem jest ciąg definiujący podstawę logarytmu naturalnego

a_n=(1+\frac{1}{n})^n

Każdy element ciągu jest liczbą wymierną, gdyż powstaje z mnożenia liczb wymiernych. Ciąg ten spełnia warunek Cauchy'ego, jest zbieżny, jednak jego granica nie istnieje w liczbach wymiernych.

\lim a_n=e\notin\mathbb{Q}

Liczba e nie jest liczbą wymierną, nie jest również liczbą algebraiczną, Liczba e jest przykładem kolejnej klasy liczb "uzupełniających braki" w liczbach wymiernych.

Liczby nienależące do zbioru liczb wymiernych, które są granicami ciągów liczb wymiernych spełniających warunek Cauchy'ego, nazywamy liczbami niewymiernymi.

Niektóre z liczb niewymiernych są liczbami algebraicznymi (np. \sqrt{2}), jednak znaczna ich większość to liczby przestępne, czyli takie, które nie są pierwiastkiem żadnego wielomianu o współczynnikach wymiernych.

\Big(\mathbb{R}, +, \times,-, \frac{\cdot}{\cdot}, \lim \Big)

Liczby zespolone jako "domknięcie" pierwiastkowania \sqrt{-1}

Podział liczb - #6

Świat szedł do przodu, matematyka odkrywała kolejne wzory opisujące rzeczywistość. W XVI wieku ponownie napotkano problem "niezupełności" liczb i działań. Trudność pojawiła się w momencie wyprowadzania wzoru na pierwiastki wielomianu stopnia 3. Każdy wielomian stopnia 3 ma przynajmniej jedno miejsce zerowe, jednak okazało się, że konstrukcja wzoru podającego te pierwiastki wymaga założenia istnienia wartości \sqrt{-1}. Tak powstały liczby zespolone, których znaczenie jest dużo bardziej głębokie niż wartość \sqrt{-1} oraz wzory Cardano dla równań sześciennych. Liczby zespolone to całkowicie nowy wymiar liczb, wymiar ukryty, mimo wszystko pojawiający się w niemal każdej empirycznej dziedzinie nauki z fizyką na czele...

... ale o tym w kolejnej części cyklu...

Pozdrowienia,

Mariusz Gromada

Mnożenie liczb ujemnych - czyli dlaczego minus razy minus daje plus

Minus razy minus daje plus

Z pewnością każdy wie, że wynikiem mnożenia liczb ujemnych jest liczba dodania. Formułka "minus razy minus daje plus" była nam wtłaczana do głów w trakcie wczesnych lat szkolnych. Nauczyciele zapomnieli jednak wyjaśnić dlaczego tak właśnie jest, oraz przybliżyć motywację matematyków definiujących arytmetykę liczb ujemnych.

Mnożenie jako skrócone dodawanie

Mówi się, że mnożenie to skrócone dodawanie, co jest w zupełności prawdą i, przy ograniczeniu do liczb całkowitych, faktem dosyć oczywistym.

3\times 4 = 3 + 3 + 3 + 3 = 4 + 4 + 4 = 12

Mnożenie jest przemienne i rozdzielne względem dodawania

Te dwie fundamentalne własności mnożenia zapisujemy jako

przemienność a\times b = b\times a

przykład 3\times 4 = 4\times 3=12

rozdzielność a\times (b+c)=a\times b + a\times c

przykład 3\times 4 = 3\times (1+3) = 3\times 1 + 3\times 3 = 3 + 9 = 12

Mnożenie liczb ujemnych z punktu widzenia matematyka

Matematycy, definiując arytmetykę liczb ujemnych, chcieli zachować spójność z już rozwiniętą arytmetyką liczb dodatnich i zera. Opierając się na interpretacji skróconego dodawania łatwo uzasadniamy następujące:

-3\times 4 = (-3)+(-3)+(-3)+(-3)=-12

"Dodając dług do długu" otrzymujemy większy dług - intuicyjne. Teraz wykorzystując przemienność mnożenia otrzymujemy:

4\times (-3)=-3\times 4=-12

W tym momencie z intuicją już trochę trudniej, natomiast spójność została zachowana. Czas przejść do meritum - tzn spróbujmy odpowiedzieć na pytanie:

-3\times (-4)=?

Do rozwiązania powyższego zastosujemy trick na bazie rozdzielność mnożenia względem dodawania.

-3\times 0=0

-3\times 0=-3\times(-4+4)=0

-3\times(-4+4)=-3\times (-4)+(-3)\times 4=0

-3\times(-4)+(-12)=0

-3\times(-4)=12

Powyższe z intuicją nie ma nic wspólnego, jednak jest spójne, tzn. na bazie arytmetyki liczb dodatnich i zera, przemienności mnożenia, rozdzielności mnożenia względem dodawania, jesteśmy w stanie uzasadnić dlaczego mnożenie liczb ujemnych musi być liczbą dodatnią.

Mnożenie liczb ujemnych jako zmniejszenie straty

Załóżmy, że mnożymy dwie liczby, gdzie interpretacja pierwszej to wartość zysku bądź starty, natomiast znaczenie drugiej to zwielokrotnienie (zwiększenie / zmniejszenie) pierwszej wartości. W takiej sytuacji mnożenie dwóch liczb ujemnych oznacza zmniejszenie straty, czyli łączny efekt dodatni działania.

Interpretacja zmniejszenia straty

Powyższe wyjaśnienie można określić mianem intuicyjnego 🙂

I na koniec film od Mathologer'a wyjaśniający powyższy problem (materiał, na którym wzorowałem powyższy wpis).

 

Pozdrowienia,

Mariusz Gromada

Spirala Ulama (spirala liczb pierwszych) - część 2 - czyli funkcja kwadratowa i zabawy z rekurencją (część 5)

W części 1 wpisu na temat Spirali Ulama zaznaczyłem, że efekt wizualnego ułożenia liczb pierwszych na diagonalach spirali kwadratowej jest konsekwencją głównie dwóch własności:

  1. Na przekątnych są albo same liczby parzyste, albo same liczby nieparzyste, zatem tylko diagonale z liczbami nieparzystymi będą agregować liczby pierwsze;
  2. Niektóre diagonale zagęszczają bardziej liczby pierwsze niż inne, co wynika z zależności pomiędzy przekątnymi i funkcją kwadratową oraz faktem, że niektóre funkcje kwadratowe generują więcej liczb pierwszych niż inne.

Dzisiejszy tekst poświęcę przybliżeniu własności nr 2.

Wielomiany i rekurencja

Funkcja kwadratowa i rekurencja

Dla wielomianów możemy zawsze podać ich postać rekurencyjną, Jest to własność mało znana, jednak dosyć prosta w uzasadnieniu. Pokażę to na przykładzie funkcji kwadratowej, jednocześnie wzbogacając cykl "Zabawy z rekurencją" 🙂

f(x) = ax^2+bx+c

Rozważmy następnie równanie

f(x+1)=f(x)+Bx+C

Podstawiając i upraszczając...

a(x+1)^2+b(x+1)+c=ax^2+bx+c+Bx+C

ax^2+2ax+a+bx+b+c=ax^2+bx+c+Bx+C

2ax+a+b=Bx+C

2a=B    oraz    a+b=C

otrzymujemy

a=\frac{B}{2}    oraz    b=C-a

Następnie analizując f(1) mamy

f(1)=a+b+c    zatem    c=f(1)-a-b

c=f(1)-a-(C-a)=f(1)-C

Wniosek: jeśli znana jest relacja rekurencyjna f(x+1)=f(x)+Bx+C oraz znamy wartość f(1) to jesteśmy w stanie jednoznacznie wskazać równanie kwadratowe ax^2+bx+c spełniające daną zależność rekurencyjna, gdzie

a=\frac{B}{2},    b=C-a,    c=f(1)-C

Uogólnienia dokonujemy na bazie dwumianu Newtona

(x+1)^n = {n\choose 0}x^n+{n\choose 1}x^{n-1}+{n\choose 2}x^{n-2}+\ldots+{n\choose {n-1}}x+{n\choose n}

Funkcja kwadratowa i linie proste / przekątne na spirali Ulama

Poniżej spróbuję pokazać w jaki sposób "nawiajnie prostej na kwadrat" sprawia, że parabole w efekcie otrzymują kształt linii prostych.

Przykład 1 - Pionowa prosta

Spirala Ulama - równanie prostej 1

Zapisujemy zależność rekurencyjną

f(1)=4

f(2)=f(1)+1+2+3+3+2

f(3)=f(2)+2+3+5+5+3

\ldots

f(n+1)=f(n)+n+2n+(2n+1)+(2n+1)+(n+1)

f(n+1)=f(n)+8n+3

Teraz, korzystając z wyprowadzonego wcześniej wzoru, wyznaczamy współczynniki a, b, c funkcji kwadratowej spełniającej f(n+1)=f(n)+8n+3.

a=\frac{8}{2}=4,    b=3-4=-1,    c=4-3=1

f(n)=4n^2-n+1

Dla testu czy wszystko jest ok sami podstawcie n=1,2,3\ldots

Przykład 2 - Przękątna (linia diagonalna)

Spirala Ulama - równanie prostej 2

Ponownie zapisujemy zależność rekurencyjną, tym razem nieco prostszą.

f(1)=3

f(2)=f(1)+2+2+3+3

f(3)=f(2)+4+4+5+5

\ldots

f(n+1)=f(n)+n+2n+2n+(2n+1)+(2n+1)

f(n+1)=f(n)+8n+2

Korzystając ze znanego wzoru wyznaczamy a, b, c dla f(n+1)=f(n)+8n+2.

a=\frac{8}{2}=4,    b=2-4=-2,    c=3-2=1

f(n)=4n^2-2n+1

W kolejnej części cyklu "o Spirali Ulama" podam wzory kilku przekątnych (czyli funkcji kwadratowych) generujących nienaturalnie dużo liczb pierwszych 🙂

Pozdrowienia,

Mariusz Gromada

Spirala Ulama (spirala liczb pierwszych) - część 1

W 1963 polski matematyk Stanisław Ulam uprzyjemniał sobie czas spędzany w trakcie "bardzo długiego i bardzo nudnego" wykładu. Rekreacja polegała na takim wypisywaniu kolejnych liczby naturalnych 1, 2, 3, ..., aby finalny kształt utworzył "spiralę kwadratową" . Poniżej przykład dla pierwszych 49 liczba naturalnych, spirala oczywiście nie kończy się na 49, chodzi jedynie o zobrazowanie zasady.

Spirala Ulama

W kolejnym kroku na tak przygotowanej "tablicy" Ulam oznaczył wszystkie liczby pierwsze

Spirala Ulamanastępnie usuwając pozostałe.

Spirala UlamaW tym momencie jego oczom ukazał się niezwykle ciekawy i nieznany dotąd wzór - tendencja do układania się liczb pierwszych na "przekątnych / liniach diagonalnych". Lepiej to obrazuje spirala wygenerowana dla znacznie większego zakresu liczb.

Spirala Ulama

Każdy z Was może wygenerować podobną spiralę używają np. tego generatora.

Spirala Ulama i parzystość / nieparzystość liczb

Nietrudno zauważyć, że na liniach diagonalnych leżą albo same liczby parzyste, albo same liczby nieparzyste. Liczby pierwsze, poza 2, są nieparzyste - zatem nic dziwnego, że układają się na przekątnych reprezentujących liczby nieparzyste. Zaskakujące jest natomiast to, że niektóre diagonale zawierają ich znacznie więcej niż inne.

Spirala Ulama i wielomiany kwadratowe

Badania nad spiralą Ulama pokazały, że wzory przez nią ujawnione mają związek z generację przez niektóre funkcje kwadratowe nienaturalnie dużej liczby liczb pierwszych (ang. prime-rich quadratic polynomials), tzn. dla niektórych f(x)=ax^2+bx+c "nienaturalnie" często f(n) jest liczbą pierwszą dla n\in\mathbb{N}. Diagonale mogą być reprezentowane przez wielomiany stopnia 2, co wyjaśniam na poniższym schemacie.

Spirala Ulama i wielomiany stopnia 2

Przeczytaj również:

Pozdrowienia,

Mariusz Gromada

 

Rekurencja pośrednia - czyli zabawy z rekurencją (część 4)

W pierwszych trzech częściach "Zabaw z rekurencją" skupialiśmy się na rekurencji bezpośredniej, tzn. na sytuacji, kiedy w ciele funkcji dochodzi do wywołania "siebie samej". Przebieg rekurencji bezpośredniej jest dość oczywisty, struktura wywołania, argumenty, jak też warunek stopu, są takie same dla wszystkich odwołań.

Rekurencja pośrednia

O rekurencji pośredniej mówimy w sytuacji"łańcucha wywołań". Przykładowo funkcja f(.) wywołuje funkcję g(.), następnie funkcja g(.) wywołuje f(.), zatem ponowne wywołanie funkcji f(.) realizowane jest bezpośrednio przez funkcję g(.), jednak pośrednio przez f(.), gdyż to f(.) wywołała g(.).

Typy rekurencji

Długość łańcucha nie musi być ograniczona, w rzeczywistości wywołania pośrednie mogą mieć nietrywialną strukturę, mogą "cofać się" do przednich elementów, "iść na skróty", "rozdzielać się", a w szczególności może dochodzić do wariantów mieszanych - tzn. wywołań bezpośrednich i pośrednich (różnego typu) w ramach jednej procedury. Dobrze to obrazuje poniższy schemat.

Rekurencja pośrednia

Aproksymacja funkcji sin(x) oraz cos(x) przy wykorzystaniu połączenia rekurencji bezpośredniej i rekurencji pośredniej

Przypomnijmy podstawowe tożsamości trygonometryczne dla wielokrotności kątów.

\sin(2x)=2\sin(x)\cos(x)

\cos(2x)=\cos^2(x)-\sin^2(x)

Równoważnie powyższe można zapisać jako

\sin(x)=2\sin\big(\frac{x}{2}\big)\cos\big(\frac{x}{2}\big)

\cos(x)=\cos^2\big(\frac{x}{2}\big)-\sin^2\big(\frac{x}{2}\big)

Zwróćmy uwagę, że znając rozwiązanie dla argumentu mniejszego \frac{x}{2} możemy podać rozwiązanie dla x – zatem tożsamości trygonometryczne są w istocie rekurencją z odwołaniami bezpośrednimi i pośrednimi! Funkcje \sin(x) w otoczeniu 0 można przybliżyć przez x, natomiast funkcję \cos(x) przez stałą wartość 1. Im mniejsze otoczenie 0 wybierzemy tym lepsza aproksymacja w zadanym przedziale, a w konsekwencji mniejszy błąd oszacowania w całości. Przyjęte wartości w otoczeniu 0 dają również pewny warunek stopu! Mamy więc wszystko co niezbędne do zastosowania strategii rekurencyjnej w aproksymacji.

Ustalmy stałą a>0 (reprezentującą otoczenie 0), następnie definiujemy dwie funkcje rekurencyjne

\text{s}(x)=\begin{cases}x&\text{dla}\quad |x|<a\\2\text{s}\big(\frac{x}{2}\big)\text{c}\big(\frac{x}{2}\big)&\text{dla}\quad |x|\geq a\end{cases}

\text{c}(x)=\begin{cases}1&\text{dla}\quad |x|<a\\\text{c}^2\big(\frac{x}{2}\big)-\text{s}^2\big(\frac{x}{2}\big)&\text{dla}\quad |x|\geq a\end{cases}

Podkreślmy ponownie, że funkcja \text{s}(x) wywołuje siebie bezpośrednio oraz wskazuje na funkcję \text{c}(x), która, oprócz bezpośredniego wywołania siebie samej, wskazuje ponownie na \text{s}(x). Jest to zatem ciekawa kombinacja rekurencji bezpośredniej z rekurencją pośrednią. Zapiszmy to w mXparser.

/* Definicja funkcji rekurencyjncyh */
Constant a = new Constant("a", 0.1);
Function s = new Function("s(x) =  if( abs(x) < a, x, 2*s(x/2)*c(x/2) )", a);
Function c = new Function("c(x) =  if( abs(x) < a, 1, c(x/2)^2-s(x/2)^2 )", a);

/* Wskazanie, ze 's' korzysta z 'c', a 'c' korzysta z 's' */
s.addDefinitions(c);
c.addDefinitions(s);

Oczekujemy, że im mniejszy parametr a>0 tym lepsza aproksymacja funkcji \sin(x) oraz \cos(x) przez odpowiednio \text{s}(x) oraz \text{c}(x). Poniżej wykresy dla a=0.5 oraz a=0.01.


/* Dane do wykresu s(x) vs sin(x) */
for (double x = -MathConstants.PI; x <= MathConstants.PI; x=x+0.02)
mXparser.consolePrintln("[ " + x +", " + MathFunctions.sin(x) + ", " + s.calculate(x) + " ],");

/* Dane do wykresu c(x) vs cos(x) */
for (double x = -MathConstants.PI; x <= MathConstants.PI; x=x+0.02)
mXparser.consolePrintln("[ " + x +", " + MathFunctions.cos(x) + ", " + c.calculate(x) + " ],");

Wniosek - proste zapisy rekurencyjne dają złożone wyniki! 🙂

Pozdrowienia,

Mariusz Gromada

Pamiętaj o:

import org.mariuszgromada.math.mxparser.*;
import org.mariuszgromada.math.mxparser.mathcollection.*;

Kod:

Zobacz również:

  1. Polowanie na czarownice - czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności - czyli zabawy z rekurencją (część 2)
  3. Naiwny test pierwszości - czyli zabawy z rekurencją (część 3)

Naiwny test pierwszości - czyli zabawy z rekurencją (część 3)

Liczby pierwsze

Jednym z najprostszych testów pierwszości jest weryfikacja czy dana liczba n posiada dzielnik z przedziału (2, \sqrt{n}) - takie podejście nazywane jest metodą naiwną - i niestety charakteryzuje się dużą złożonością obliczeniową. Nawet przy wykorzystaniu Sita Eratostenesa złożoność obliczeniowa sięga \frac{\sqrt{n}}{\log{n}}. Jednak w cyklu "Zabawy z rekurencją" nie bardzo zwracamy uwagę na złożoność 🙂 , bardziej chodzi o zobrazowanie jak całe algorytmy mogą być łatwo zapisane w postaci krótkich matematycznych funkcji rekurencyjnych - zatem do dzieła 🙂

Rekurencyjne poszukiwanie dzielników

Naszym zadaniem będzie zdefiniowanie funkcji zwracającej 1 jeśli podana liczba n jest liczbą pierwszą oraz 0 w przeciwnym wypadku. Zacznijmy jednak od podania funkcji weryfikującej czy liczba posiada dzielniki.

{\small\text{CzyDzielnik}(n, a, b)=}

{\small=\begin{cases}0&\text{dla}\quad a>b\\1&\text{dla}\quad n \mod a=0\\ \text{CzyDzielnik}(n, a+1, b)&\text{w inn. przyp.}\end{cases}}

Powyższa funkcja zwraca 1 jeśli liczba n posiada dzielnik z przedziału (a,b), oraz 0 w przeciwnym wypadku. Następnie definiujemy wyrażenie reprezentujące naiwny test pierwszości.

{\small\text{CzyPierwsza}(n)=}

{\small=\begin{cases}0&\text{dla}\quad n<2\\ \neg\text{CzyDzielnik}(n,2,\sqrt{n})&\text{dla}\quad n>=2\end{cases}}

Rolą funkcji "CzyPierwsza" jest jedynie "wprawienie algorytmu w ruch" oraz zwrócenie negacji wyniki funkcji "CzyDzielnik". Proste prawda? 🙂 Sprawdźmy więc w mXparser czy to faktycznie działa.

/* Definicja funkcji rekurencyjnych */
Function CzyDzielnik = new Function("CzyDzielnik(n, a, b) = if( a>b, 0, if( n%a = 0, 1, CzyDzielnik(n, a+1, b) ) )");
Function CzyPierwsza = new Function("CzyPierwsza(n) = if( n<2, 0, ~CzyDzielnik(n, 2, sqrt(n)) )", CzyDzielnik);

/* Obliczenie i wyświetlenie wartości */
mXparser.consolePrintln( "CzyPierwsza(1) = " + CzyPierwsza.calculate(1) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(2) = " + CzyPierwsza.calculate(2) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(3) = " + CzyPierwsza.calculate(3) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(4) = " + CzyPierwsza.calculate(4) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(5) = " + CzyPierwsza.calculate(5) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(6) = " + CzyPierwsza.calculate(6) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(7) = " + CzyPierwsza.calculate(7) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(8) = " + CzyPierwsza.calculate(8) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(9) = " + CzyPierwsza.calculate(9) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(10) = " + CzyPierwsza.calculate(10) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );

+ wynik

CzyPierwsza(1) = 0.0, czas oblicz. = 0.08 s.
CzyPierwsza(2) = 1.0, czas oblicz. = 0.03 s.
CzyPierwsza(3) = 1.0, czas oblicz. = 0.026 s.
CzyPierwsza(4) = 0.0, czas oblicz. = 0.022 s.
CzyPierwsza(5) = 1.0, czas oblicz. = 0.038 s.
CzyPierwsza(6) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(7) = 1.0, czas oblicz. = 0.028 s.
CzyPierwsza(8) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(9) = 0.0, czas oblicz. = 0.053 s.
CzyPierwsza(10) = 0.0, czas oblicz. = 0.011 s.

Wygląda na to, że obliczenia są poprawne! Teraz możemy zweryfikować ile jest liczb pierwszych w podanym przedziale, definiując

\pi(n)=\sum_{i=1}^n \text{CzyPierwsza}(i)

/* Definicja wyrażenia sumującego wynik funkcji CzyPierwsza */
Expression pi100 = new Expression("sum(i, 1, 100, CzyPierwsza(i) )");
pi100.addFunctions(CzyPierwsza);

/* Obliczenie i wyświetlenie wyniku */
mXparser.consolePrintln( "Liczba liczb pierwszych w przedziale (1,100) = " + pi100.calculate());

+ wynik

Liczba liczb pierwszych w przedziale (1,100) = 25.0

Pozdrowienia,

Mariusz Gromada

Pamiętajcie, że uruchamiając kody mXparsera należy dodać w nagłówku:

import org.mariuszgromada.math.mxparser.*;

Kod:

 

Zobacz również:

  1. Polowanie na czarownice - czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności - czyli zabawy z rekurencją (część 2)
  3. Rekurencja pośrednia - czyli zabawy z rekurencją (część 4)

mXparser - wysoce elastyczny parser (interpreter) wyrażeń matematycznych dla JAVA oraz C# .NET

mXparser - parser matematyczny

Serdecznie zapraszam do zapoznania się z wysoce elastycznym interpreterem wyrażeń matematycznych. Oprogramowanie jest mojego autorstwa, powstało w 2010 roku i wtedy zostało opublikowane w serwisie SourceForge.net. Z racji, że teraz posiadam stronę o odpowiedniej tematyce, zdecydowałem się przygotować dedykowany opis, który znajdziecie pod tym linkiem. Dostępne są również tutorial oraz specyfikacja API.

Pozdrowienia,

Mariusz Gromada

Pobierz mXparser - parser matematyczny

Download mXparser

Download mXparser

Liczba Stirlinga II rodzaju i losowanie ze zwracaniem

Losowanie ze zwracaniem

Jakiś czas temu rozważałem problem losowania ze zwracaniem dokładnie n-elementów z n-elementowego zbioru (dla uściślenia w zbiorze wyjściowym znajduje się dokładnie n-różnych elementów). W wyniku takiej operacji w wylosowanej próbie mogą pojawić się duplikaty - załóżmy zatem, że otrzymaliśmy k unikalnych rezultatów (oczywiście 1 ≤ k ≤ n). Naturalnie pojawiło się pytanie kombinatoryczne.

Liczba sposobów otrzymania k-unikalnych rezultatów

Ile istnieje sposobów takiego wylosowania (ze zwracaniem) n-elementów spośród n-elementowego zbioru, że w wyniku otrzymamy dokładnie k-unikalnych rezultatów?

Liczbę takich sposobów oznaczmy przez B(n,k).

No i się zaczęło "kombinowanie", początkowo wychodziłem od losowania k różnych elementów, w kolejnym kroku planując dodanie losowania n-k z wylosowanych wcześniej k. Tego typu rozumowanie prowadziło do bardzo skomplikowanych rozważań, szczegóły pominę. Na rozwiązanie wpadłem po około 2 dniach.

Pierwszy krok - wariacja bez powtórzeń

Ddość standardowy - liczba sposobów wyboru k różnych elementów z n zwracając uwagę na kolejność - jest to wariacja bez powtórzeń - V(n,k).

Drugi krok - liczba Stirlinga II

przestajemy myśleć, że właśnie wylosowaliśmy k unikalnych i należy jeszcze dolosować n-k (choć to prawda). W zamian ustalamy, że mamy już n wylosowanych elementów, w tym k unikalnych. Zabieg myślowy polega teraz na uzmysłowieniu faktu, że mając k różnych elementów w zbiorze n-elementowym, dokonaliśmy jego podziału na k-podzbiorów. Ile mamy sposobów podziału n-elementowego zbioru na k-podzbiorów? Jest to właśnie liczba Stirlinga II rodzaju oznaczona S2(n,k). Zatem finalnie

B(n,k) = V(n,k)*S2(n,k)

Dlaczego w kroku pierwszym zwracaliśmy uwagę na kolejność? Chętnych zapraszam do komentowania 🙂

Pozdrowienia,

Mariusz Gromada