Nopeasti kasvavia funktioita/lukujonoja

Tutkin tässä tarinassa joitakin kasvavia lukujonoja. Jotkut jonot kasvavat vikkelämmin kuin toiset. Aloitetaan potenssifunktiosta ja lopetetaan Ackermannin lukuihin. Tarinassa on mukana muutamia tehtäviä, joista toiset ovat helpompia ja toiset vaikeampia.  Täytyy tunnustaa, että en itse osaa ratkaista kaikkia ongelmiani :o)

Aika monen tehtävän ”vastaus” löytyy suoraan tekstistä. Tehtävissä on tietysti ideana, että ratkaisija itse ratkaisee ongelmat omilla menetelmillään.

Koska alaindeksien kanssa puuhasteleminen on hidasta samaistan lukujonot funktioihin.

hiekanlaskija

Arkhimedes (noin 287 – 212  eaa)  pohti, miten määritellä suuria lukuja. Noihin aikoihin kreikkalaisilla suurin nimetty luku oli myriadi = 10000. Hiekanlaskijaksi kutsutussa artikkelissaan, tai paremminkin Syrakusan kuningas Gelonille osoitetussa kirjeessä, hän kehitti matemaattisen menetelmän kuvata suuria lukuja. Hän perusti lukujärjestelmänsä lukuun 10002 = 100000000 = 108 = a. Arkhimedeksen tarinassa esitetty suurin luku on 

\left(a^a\right)^a=10^A

missä A = 8·1016. Varmaankin kaikki tarinan ajatuksella lukeneet ovat ymmärtäneet, että lukujen määrittämistä voi jatkaa aina suurempiin ja suurempiin lukuihin.

Jotta saadaan jonkinlainen kuva funktioiden kasvunopeudesta, niin otetaan yhdeksi vertailukohdaksi iso luku, vaikkapa googol eli  10100 = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000. Ennen vanhaan 9.99999999·1099 oli suurin luku, jota perinteiset funktiolaskimet osasivat käsitellä, eli googol oli liian luku laskimille.

Arkhimedes laski Hiekanlaskijassaan että maailmankaikkeuteen mahtuisi alle 1063 hiekanjyvää, nykytietämyksen mukaan hiekanjyvien lukumäärä olisi noin 1096. Jos maailmankaikkeus täytettäisiin atomeilla, niin siihen saataisiin mahtumaan noin 10110  atomia.

Tehtävä 1. Osoita, että Arkhimedeen suuressa luvussa kymmenen potenssi on A = 8·1016.

Tehtävä 2. Laske kuinka monta hiekanjyvää mahtuisi koko tunnettuun maailmankaikkeuteen.

potenssi/polynomifunktio

Polynomit/potenssifunktiot kasvavat vikkelästi, kun asteluku on iso. Kuvassa on polynomien xn kuvaajat,  kun n saa arvot 1, …, 100.

Otetaan esimerkiksi kymmenennen asteen potenssifunktio x^10. Lukujonona se olisi ax = (10, 100, 1000, 10000, …). Googol saavutetaan jo x:n arvolla 1000000000. 

Tehtävä 3. Ratkaise yhtälö x^10 = googol

Tehtävä 4. Derivoi funktio f(x) = x^10.

Tehtävä 5. Integroi funktio f(x) = x^10.

eksponenttifunktio

Eksponenttifunktiot ax, kun a > 1, kasvavat nopeasti suurilla x:n arvoilla. Riittävän suurilla x:n arvoilla, ne kasvavat nopeammin kuin potenssifunktiot. 

Otetaan esimerkiksi potenssifunktio f(x) = x10 ja eksponenttifunktio g(x) = 10x. Aluksi potenssifunktion arvot ovat selvästi suurempia kuin eksponenttifunktion arvot, lopulta kuitenkin eksponenttifunktio ohittaa potenssifunktion. Eksponenttifunktio g(x) = 10 saavuttaa googolin x:n arvolla 100.

Tehtävä 6. Ratkaise yhtälö x10 = 10x.

Tehtävä 7. Ratkaise yhtälö 10x = googol.

Tehtävä 8. Derivoi g(x) = 10x .

Tehtävä 9. Integroi g(x) = 10x .

Tehtävä 10. Todista, että riittävän suurilla x:n arvoilla eksponenttifunktion ax, a > 0 arvot ovat suurempia kuin potenssifunktion xn arvot. Eli että on olemassa … muotoile itse lauseesi.

kertoma

Kertomafunktio kertoo kuinka monella eri tavalla joukon alkiot voidaan laittaa eri järjestykseen. Esimerkiksi viisi korttia voi olla 5*4*3*2*1 = 120 eri järjestyksessä. 

x!=x\cdot\left(x-1\right)...·2\cdot1

Kertomafunktion kertolaskuun perustuva määritelmä pätee vain luonnollisille luvuille (0! = 1), mutta se voidaan määritellä myös siten, että x voi olla mikä tahansa reaaliluku. Niinpä esimerkiksi luvun pii kertoma on noin 7.188. Määrittelyn apuna käytetään gamma-funktiota, jolle pätee 𝛤(n) = (n – 1)!. Gamma-funktio löytyy myös GeoGebrasta, Nspirestä (valitettavasti koneessani ei enää ole Nspireä) ja Speedcrunch-ohjelmasta.

Kertomafunktion x! kasvu on vikkelää. Googol ylitetään x:n arvolla 70.

Vertaillaan eksponenttifunktion 10x ja kertomafunktion x! arvoja. Alla Pythonilla tuotettu taulukko, josta näkee, että kertomafunktio ohittaa eksponenttifunktion 10x arvot kun x = 25.

Kuvassa on kertomafunktion  ja eksponenttifunktion logaritmien kuvaajat: ln(x!) ja ln(10^x).

Kertomafunktiolle pätee yksinkertainen likimääräiskaava nimeltään Stirlingin kaava. 

x!\approx f\left(x\right)=\sqrt{2\pi x}\left(\frac{x}{e}\right)^x

Tehtävä 11. Ratkaise x! = googol, likiarvo varmaankin riittää.

Tehtävä 12. Ratkaise yhtälö 10x = x!. Jos haluat tutkia vain luonnollisia lukuja, niin muotoile itse ongelmasi tyyliin, mikä on ensimmäinen luonnollinen luku x, jolla …

Tehtävä 13. Derivoi Stirlingin funktio f(x).

Tehtävä 14. Integroi Stirlingin funktio f(x) :o)

Tehtävä 15. Todista, että kertomafunktion x! arvot ovat suurempia kuin eksponenttifunktion ax riittävän suurilla x:n arvoilla.

xx

Tämän tyyppiselle funktiolla ei varsinaisesti ole omaa nimeä, x potenssiin x kelvannee. Toki sitä voidaan merkitä tetraatiolaskutoimitusmerkinnällä 2x tai x↑2. Palataan näihin merkintöihin kohtapuoliin. Funktion xx arvot ylittävät googolin  x:n arvolla 57.

Tehtävä 16. Ratkaise yhtälö xx = googol.

Tehtävä 17.  Derivoi f(x) = xx.

Tehtävä 18.  Integroi f(x) = xx :o)

Tehtävä 19.  Todista, että xx > x!, kun x > 1.

Tehtävä 20. Määritä funktion f(x) = xx pienin arvo, kun x > 0.   

hyperkertoma

Kertomafunktiossa luku kerrotaan sitä pienemmillä positiivisillä luonnollisilla luvuilla

Luvun x hyperkertomalla tarkoitetaan lukua, joka saadaan kun xx kerrotaan x:ää pienempien pienempien luonnollisten lukujen x >0  potensseilla itsensä kanssa.H\left(x\right)=x^x\cdot\left(x-1\right)^{x-1}...\ 2^2\cdot1^1=\prod_{i=1}^xi^i

Myös H voidaan määritellä jatkuvaksi kaikilla reaaliluvuilla K-funktion avulla. Sitä ei löydy GeoGebrasta :o( 

Hyperkertoma ylittää googolin kun x = 15. Alla olevassa taulukossa hyperkertomafunktio on hk(x).

Kuvaajassa xx:n ja hyperkertoman kymmenkantaiset logaritmit.

Tehtävä 21. Luo omalla laskinohjelmistollasi tai käyttämälläsi ohjelmointikielellä funktio, joka laskee hyperkertoman arvoja. Laske H(13) ja H(23) esitä tulos kymmenpotenssimuodossa..

Tehtävä 22. Ratkaise millä x:n arvolla H(x) ylittää googolin.

Tehtävä 23. Todista, että kakkosta suuremmilla x:n arvoilla H(x) on suurempi kuin xx.

Tehtävä 24. Osoita, että H(5) on yhtä suuri kuin vuorokauden pituus millisekunteina.

tetraatio

Tetraatiota pidetään neljäntenä laskutoimituksena yhteenlaskun, kertolaskun ja  potenssiin korottamisen jälkeen. Rudy Ruckerin merkitsemistavalla 

_{}^{b}a=\underbrace{a^{a^{a^{.^{.}}}}}_\textrm{b kpl}

Esimerkiksi kaksi tetratoituna kolmeen 32 (vai olisiko parempi sanoa kaksi tetratoituna kolmanteen)

_{ }^32=2^{2^2}=2^4=16

Potenssien potenssien … potensseja voidaan kutsua myös potenssitorneiksi. Edellisen esimerkin 32 on kolmannen kertaluokan potenssitorni kakkosia.

Funktio, jossa x tetratoidaan itsellään T(x) = xx kasvaa tosi nopeasti.

T\left(1\right)=1
T\left(2\right)=\ _{ }^22=2^{2^{ }}=4
T\left(3\right)\ =\ _{ }^33=3^{3^3}=3^{27}=7625597484987

T(4) on jo niin suuri luku, että en osaa laskea sen arvoa. Sen suuruusluokka on noin 10N, missä N ≈ 8·10153.

Tehtävä 25. Osoita, että T(4) on noin 10N, missä N ≈ 8·10153

Tehtävä 26. Todista, että T(x) > H(x), kun x > 2.

Ackermannin lukujono

Tetraatiota voidaan merkitä myös nuolimerkinnällä. Donald Knuth kehitti merkitsemistavan 1970-luvulla.

Nuolimerkinnällä potenssiin korotus on

a\uparrow b=a^b

ja tetraatio

a\uparrow\uparrow b=\underbrace{a\uparrow a\uparrow...a}_\textrm{b kpl} =\ _{ }^ba

Näillä nuolilla päästään helposti vielä vikkelämmin kasvaviin funktioihin,

a\uparrow\uparrow\uparrow  b=\underbrace{a\uparrow\uparrow a\uparrow\uparrow ...\uparrow\uparrow a}_\textrm{b kpl}

ja niin edelleen.

Vuonna 1928 Wilhelm Ackermann määritti rekursiivisen funktion A(m, n, p), jätän sen määritelmän opiskelun lukijan harteille. Alun perin funktion määritelmässä oli kolme muuttujaa, nykyään se määritellään rekursiivisesti yleensä kahdella muuttujalla A(m, n). Ackermannin funktio kasvaa sanoisinko sairaan nopeasti. Ackermannin funktiosta voidaan johtaa lukujono, jota Conway ja Guy kutsuvat Ackermannin luvuiksi. Niiden lukuarvot voidaan laskea nuolimerkinnällä merkittynä

A\left(n\right)\ = n \underbrace{\uparrow \uparrow...\uparrow}_\textrm{n kpl}n

Ackermannin funktion arvot eli Ackermannin lukujonon arvot kasvavat aika vikkelästi. 

Tehtävä 27. Laske A(1) ja A(2)

Tehtävä 28. Kuinka monta kolmosta on korotettuna luvussa A(3).

Tehtävä 29. Laske A(3):n likiarvo kymmenpotenssimuodossa.

Tehtävä 30. Keksi jokin mielekäs tapa esittää kuinka suuri on A(4).

Conwayn ja Guyn funktio

Lupasin päättää tarinan Ackermannin lukuihin, mutta laitetaan tänne loppuun vielä nopeammin kasvava funktio. Kirjassaan The Book of Numbers John Horton Conway ja Richard K. Guy esittävät merkintätavan, jota he kutsuvat nimellä ketjutettu nuoli (chained arrow). Siinä käytetään apuna Knuthin nuolia.

a\rightarrow b\rightarrow c\ = a \underbrace{\uparrow \uparrow...\uparrow}_\textrm{c kpl} b

Jätän tämänkin funktion tarkemman määritelmän tutkimisen asiasta kiinnostuneille. Conway ja Guy esittävät lukujononsa muodossa

CG(1) = 1

CG(2) = 2 →2

CG(3) = 3 →3→3

CG(4) = 4→4→4→4

jne.

Seuraavia tehtäviä varten kannattaa opiskella ketjutetun nuolen määritelmä vaikkapa sivulta https://en.wikipedia.org/wiki/Conway_chained_arrow_notation

Tehtävä 31. Osoita, että CG(1) = A(1)

Tehtävä 32. Osoita, että CG(2) = A(2)

Tehtävä 33. Osoita, että CG(3) = A(3)

Tehtävä 34. Osoita, että CG(4) on aika paljon suurempi kuin  A(4).

Tehtävä 35. Mikä on Grahamin luku = G (liittyy graafiteoriaan)? Mikä on ensimmäinen x:n arvo, jolla A(x) > G? Mikä on ensimmäinen x:n arvo, jolla CG(x) > G?

Tehtävä 35. Kehitä vielä nopeammin kasvava lukujono.

rahaa tarjolla

Ratkaise tehtävät 1 – 35 ja kirjoita siisti ratkaisut. Tallenna ratkaisusi pdf:ksi ja lähetä se minulle m miukumauku hyl.fi Ensimmäinen ratkaisuja, joka on ratkaissut minun mielestäni oikein yli 30 tehtävää saa palkkioksi A(1):n verran euroja.

lähteet

Hiekanlaskija englanniksi Wikipediassa
https://en.wikipedia.org/wiki/The_Sand_Reckoner

Hiekanlaskijalukuja Scientific Gems-blogissa
https://scientificgems.wordpress.com/2018/04/05/the-sand-reckoner/

Hiekanlaskija teksti englanniksi
https://www.sacred-texts.com/cla/archim/sand/sandreck.htm

Googol Wikipediassa
https://fi.wikipedia.org/wiki/Googol

Gammafunktio Wikipediassa
https://fi.wikipedia.org/wiki/Gammafunktio

Hyperfactorial Wikipediassa
https://en.wikipedia.org/wiki/Hyperfactorial

Tetraatio wikipediassa
https://en.wikipedia.org/wiki/Tetration

Ackermannin funktio Wikipediassa
https://en.wikipedia.org/wiki/Ackermann_function

Ackermannin luvut Mathematics Domainissa
https://arbital.com/p/ackermann_function/

Conway chained arrow notation Wikipediassa
https://en.wikipedia.org/wiki/Conway_chained_arrow_notation#Ackermann_function

Higher-Order Recursion Abstraction: How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking, Baltasar Trancón y Widemann
https://arxiv.org/abs/1602.05010

Graham’s number Wikipediassa
https://en.wikipedia.org/wiki/Graham%27s_number

Kirjoja

Conway, Guy. The Book of Numbers, Copernicus, 1998. Luku: Some Very Large Numbers.

Gardner. Penrose Tile to Trapdoor Ciphers. Freeman, 1989. Luku: Ramsey Theory. 

Rucker. Infinity and the Mind. Birkhäuser, 1982. Luku: All the Numbers. Art Housella Mieli ja Äärettömyys.

Merkkijonometodit esimerkeillä

Pari viikkoa sitten julkaisin ”Listametodit esimerkeillä” – artikkelin. Tein samanlaisen Pythonin merkkijonometodeista. Mikään näistä ei muuta alkuperäistä merkkijonoa. Tarinan lopussa on linkki Colab-tiedostoon.

Minä ole käyttänyt näistä enimmäkseen join ja replace -metodeja omissa koodinpätkissäni.

Colab-tiedosto on täällä.

Listametodit esimerkeillä

Tein lähinnä itselleni esimerkkitiedoston Pythonin listametodeista. Samalla tuli käytyä läpi nämä kaikki. Samalla tuli opittua pari uutta asiaa. Yleensä käytän vain append()-metodia koodeissani.

Listametodit muuttavat tai antavat tietoa listasta. Tarinan lopussa on mukana linkki Colab-tiedostoon.

Seuraavaksi pitää tehdä samanlainen merkkijonometodeista. Niitä vaan on niin paljon.

Colab-tiedosto löytyy täältä. https://colab.research.google.com/drive/1I2M_OYDqLBfCLzdd5vVf36CfbpQ3J1hM?usp=sharing