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 1000² = 100000000 = 10⁸ = a. Arkhimedeksen tarinassa esitetty suurin luku on 

missä A = 8·10¹⁶. 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  10¹⁰⁰ = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000. Ennen vanhaan 9.99999999·10⁹⁹ oli suurin luku, jota perinteiset funktiolaskimet osasivat käsitellä, eli googol oli liian luku laskimille.

Arkhimedes laski Hiekanlaskijassaan että maailmankaikkeuteen mahtuisi alle 10⁶³ hiekanjyvää, nykytietämyksen mukaan hiekanjyvien lukumäärä olisi noin 10⁹⁶. Jos maailmankaikkeus täytettäisiin atomeilla, niin siihen saataisiin mahtumaan noin 10¹¹⁰  atomia.

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

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 xⁿ kuvaajat,  kun n saa arvot 1, …, 100.

Otetaan esimerkiksi kymmenennen asteen potenssifunktio x^10. Lukujonona se olisi a_x = (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 a^x, 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) = x¹⁰ ja eksponenttifunktio g(x) = 10^x. 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ö x¹⁰ = 10^x.

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

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

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

Tehtävä 10. Todista, että riittävän suurilla x:n arvoilla eksponenttifunktion a^x, a > 0 arvot ovat suurempia kuin potenssifunktion xⁿ 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ä. 

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 10^x ja kertomafunktion x! arvoja. Alla Pythonilla tuotettu taulukko, josta näkee, että kertomafunktio ohittaa eksponenttifunktion 10^x 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. 

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

Tehtävä 12. Ratkaise yhtälö 10^x = 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 a^x riittävän suurilla x:n arvoilla.

x^x

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

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

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

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

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

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

hyperkertoma

Kertomafunktiossa luku kerrotaan sitä pienemmillä positiivisillä luonnollisilla luvuilla

Luvun x hyperkertomalla tarkoitetaan lukua, joka saadaan kun x^x kerrotaan x:ää pienempien pienempien luonnollisten lukujen x >0  potensseilla itsensä kanssa.

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 x^x: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 x^x.

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 

Esimerkiksi kaksi tetratoituna kolmeen ³2 (vai olisiko parempi sanoa kaksi tetratoituna kolmanteen)

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

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

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

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

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

ja tetraatio

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

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ä

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.

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.