XII. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2009. május 15–17
Fibonacci-számok és fraktálok TDK dolgozat Erős Levente Sapientia – Erdélyi Magyar Tudományegyetem Műszaki- és Humántudományok kar, Marosvásárhely Informatika szak
Témavezető tanár: dr. Bege Antal, egyetemi docens Sapientia – Erdélyi Magyar Tudományegyetem Műszaki- és Humántudományok kar, Marosvásárhely Matematika-Informatika tanszék
Kivonat A Fibonacci sorozat számos alkalmazásával, érdekes kutatások kiindulópontja a diszkrét matematikában. A sorozat alaptulajdonságai már középiskolából ismertek, azonban ma is rengeteg új eredménnyel találkozunk. Ilyen új fogalom a Fibonomiális-együtthatók és képletek fogalma. Ezeket a fogalmakat vizsgáljuk a Pascal illetve a Binomiális-képlet segítségével. A Sierpinski háromszögekhez hasonló, fraktálszerű környezetet vezetünk be a Pascal háromszögre és a Fibonomiális háromszögre, az elemek oszthatósági tulajdonságait vizsgálva. A technika mai állása szerint egy számítógép alapszintű erőforrásainak kiaknázása nem elegendő ezen számítások elvégzésére. Ezért válik szükségessé egy olyan általánosítás további kutatása, mely segítségével megvalósítható a kitűzött feladat.
2
Tartalomjegyzék I. Bevezetés .................................................................................................................... 4 II. A Fibonomiális sorozat ............................................................................................. 6 II.1 A Fibonacci hatványok ...................................................................................... 6 II.2 Binomiális együtthatók és összefüggések ......................................................... 9 III. A Fibonomiális fraktálok vizsgálatának módszerei ................................................. 11 III. 1. Két módszer a Fibonomiális tábla felírására ................................................ 11 III. 1. 1. Fibonacci faktoriális ............................................................................. 11 III. 1. 2. Fibonomiális formula ........................................................................... 12 III. 1. 3. Általános formula ................................................................................. 14 III. 2. A fibonomiális fraktálok rajzolása ................................................................. 16 III. 2. 1. A tábla elemeinek kiszámítása .............................................................. 16 III. 3. 2. A fraktálok rajzolása ............................................................................. 18 IV. Eredmények ............................................................................................................. 19 IV. 1. Fraktálok a Pascal-háromszögből ................................................................... 21 IV. 2. Összehasonlítás ............................................................................................... 23 Könyvészet ..................................................................................................................... 25
3
I. Bevezetés A Fibonacci számok eredetüket tekintve megelőzték a matematikust, kiről elnevezésüket kapták. A sorozatot először 1150-ben írta le két indiai matematikus, miközben a szanszkrit költészet elméleti kérdéseit vizsgálva ütköztek egy összegre bontási problémába. Azt a kérdést vizsgálták, hogyan lehet rövid és hosszú szótagokkal kitölteni egy időtartamot, ha egy hosszú szótag két rövidnek felel meg. Ők voltak Gopala és Hemacsandra. Azonban tőlük függetlenül, nyugaton Leonardo Fibonacci, 1202-ben szintén megtalálta a sorozatot, miközben egy nyúlcsalád növekedését vizsgáló gyakorlófeladatot adott fel a Liber Abaci című könyvében. Később Lucas róla nevezte el a Fibonacci-sorozatot. A 17. században újra felfedezte Kepler a sorozatot, amelyet természeti jelenségekkel hozott
kapcsolatba. Egyes megállapítások szerint sorozat tagjai a természetben gyakran fordulnak elő, például a virágok szirmainak számában: átalában ezek a növényeknek Fibonacci szám mennyiségű szírmuk van. A
Fibonacci-számoknak
számos
érdekes
alkalmazásaira
bukkanhatunk
különböző
szakirodalmak olvasásakor. Említsünk meg itt nényányat:
Egy n hosszú szakaszt Fn + 1-féleképpen lehet kirakni 1 és 2 hosszú szakaszokból. Egy 2×n-es sakktáblát 2×1-es dominókkal Fn + 1-féleképpen lehet lefedni.
Az 1, 2, ... n számokból Fn + 2-féleképpen lehet kiválasztani egy részhalmazt úgy, hogy ne kerüljenek bele szomszédos számok (1-et és n-t is szomszédosnak tekintve).
Azoknak a bitsorozatoknak a száma, amelyekben nincs két egymást követő 0, Fn + 2; annak az esélye, hogy n egymást követő pénzfeldobás során nem kapunk kétszer egymás után fejet, Fn + 2 / 2n.
Minden pozitív egész szám felírható különböző Fibonacci-számok összegeként; ha a Fibonacci-számok között nem lehet két egymást követő, akkor a felírás egyértelmű. Ez a Zeckendorf-tétel, maga a felírás pedig Zeckendorf-reprezentáció vagy Fibonacciszámrendszer néven ismeretes.
4
A mérföld és a kilométer közötti váltószám (1,609) közel van az aranymetszéshez, ezért a kettő közötti átváltás közelíthető egy bitenkénti eltolás művelettel a Fibonacciszámrendszerben.
A Fibonacci sorozat matematikai alapfoglamait már középiskolában megismerhettük, uugyanúgy mint a Pascal háromszögét, amely kedvelt téma a kezdő informatikus oktatásában. Hasonlóképp a Fibonacci sorozat, a rekurzió egy iskolapéldája, mivel a sorozat tagjait egy egyszerű rekurzív képlet segítségével előállíthatjuk. Ismerünk továbbá számos összefüggést a Fibonacci-számok és a binomiális együtthatók között. Sőt mi több, a binomiális együtthatókéhoz hasonló felírást vezetünk be a továbbiakban, amelyek megadják az úgynevezett Fibonomiális együtthatókat. Ha a Fibonacci hatványok vizsgálatába kezdünk eljuthatunk egy, a Binomiális együtthatókból felépített háromszöghöz hasonló táblához, amelyet Fibonomiális táblának vagy háromszögnek neveznek. A háromszög hasonló a Pascal féle háromszöghöz, amelyből szintént különböző oszthatósági mintákat rajzolhatunk, avagy fraktálokat, akárcsak Fibonomiális együtthatókból. Ezt az elemek oszthatóságát vizsgálva tehetjük meg. A tábla elemeit rendre osztjuk és a kapott maradékosztáléyokat színezzük, annak függvényében, hogy osztják az elemet, vagy nem.
5
II. A Fibonomiális sorozat
II.1 A Fibonacci hatványok Ahogy fennáll a minden egyes Fibonacci-számra az ismert rekurzív képlet, miszerint minden Fibonacci szám megkapható az előző kettő összegeként, úgy felírható ezek k-ad fokú hatványa kifejezés elsőfokú hatvány. A másodfokú hatvány
is. Belátható, hogy az
felírására több módszer is van. Az első lehetőség, hogy felírjuk a Fibonacci-számokat explicit alakjukban, továbbá kikötjük
Ahol n
, míg
és
:
. Mindkét oldalt négyzetre emelve, egy három tagú
összeget kapunk, amelyből selythető, hogy a másodfokú hatvány három előző tagra épül. A megjelenő kifejezés a -1-nek (n+1) hatványú lineáris kombinációja:
Ebből következik a rekuzrzív kifejezés, amely az előzőleg kiszámított három tagra épül:
A képlet alapján egyszerűen írhatók fel a nyégyzetes Fibonacci számok, csak az előző három tag ismeretére kell hagyatkoznunk, így az (1) táblázatban összefoglalva könnyen számolhatunk velük.
6
1.táblázat A négyzetes Fibonacci számok 0
1
2
3
4
5 ...
1
1
2
3
5
8 ...
1
1
4
9
25
64 ..
A szabályt a harmadik hatvány megtalálására Zeitlin és Parker tették közzé 1963-ban a Fibonacci Szövetség hivatalos publikációjában, a Fibonacci Quarterly-ben [6]. A formula a következő:
Felmerül a fenti minta általánosíthatóságának kérdese. Ha tudunk általánosítani, akkor a negyedik hatványt a következő formában várjuk:
Öt ismeretlenünk van, A,B,C,D és E, amelyeket megkaphatunk, úgy hogy a tagokat baloldalra írva felírunk öt darab egyenletet és behelyettesítünk rendre kis Fibonacci számokat. Például az első egyenlet ismeretleneinek együtthatóit helyettesítjük
Fibonacci-
számokkal. A másodikat a következő hat Fibonacci-számmal és így tovább. Az így kapott egyenlet rendszer megoldását számítógépre bízzuk. A Matlab matematikai szoftvercsomag lehetővé teszi ezt számunkra. Így gyorsan megkaphatjuk a végleges negyedik hatványt is, mután visszavisszük a megfelelő tagokat a jobboldalra:
Az ötödik formula az előbbi módszerrel szintén megkapható:
7
A fentebb kiszámított hatványokat egymás alá felírva a binomiális együtthatók esetében látott kifejezésekhez hasonló sorokhoz jutunk, melyeknek az együtthatói adják majd a Fibonomiális táblát. Ezek az együtthatók hasonlatosak a binomiális együtthatókhoz és Fibonomiális számoknak is nevezik őket. Ha bevesszük a 0-dik hatványt is, ami
, és háromszög alakban írjük fel az
egyenleteket, megkaphathatjük az együtthatókból a Fiboniális tábla egy változatát, amely nem tartalmaz negatív előjelű együtthatót. Az együtthatókat felírva, több tulajdonságra is rájövünk. Az első átlón levő számok Fibonacci számok, az együtthatók előjelei páronként váltakoznak, és az előjeleket elhagyva, szimmetriát figyelhetünk meg az elemek között, a függőleges tengelyre nézve. -1 -1 -1 -1
1 1
2 3
1 2
6
-1 -3
-1
A megjelenő háromszög sokban hasonlít Pascal háromszögére, viszont valamicskét bonyolultabb összefüggést őriz az elemek között, amelyről a későbbiekben szólunk. Most lássuk kicsitt közelebbről a binomiális együtthatókat, hogy jobban megértsük a későbbi összefüggéseket köztük és a mi Fibonacci számaink között.
8
II.2 Binomiális együtthatók és összefüggések Remélhetőleg sokak számára ismerős Pascal háromszöge, amely az úgynevezett binomiális együtthatókat tartalmazza, melyek a következő egyenletek együtthatói: (1+x)0 =1 (1+x)1 =1+x (1+x)2 =1+ 2 x + 1 x2 (1+x)3 =1+ 3 x+ 3 x2+ 1 x3 (1+x)4 =1+ 4 x+ 6 x2+ 4 x3+ 2 x4
Ha sorban vesszük az egyenleteket és oszlopokban az együtthatókat, akkor azok kiszámíthatók egyszerűen a kombinációs képlet segítségével, lévén n elem, k-adik osztályú kombinációja adja az n-dik sorban levő k-adik elemet. A kombináció képlete középiskolából ismert. A Pascal háromszögben megtalálhatóak a Fibonacci számok, habár igen nehéz őket észrevenni. Ha a ferde átlókon haladva összeadjuk a számokat, akkor megkaphatjuk sorban az említett számokat. 1.ábra - Pascal háromszöge és az átlók összegeként kapott Fibonacci számok
9
Az általános képlet a Pascal-háromszögből kiszámolt Fibonacci-számokra:
A Pascal háromszög minden egyes eleme kiszámítható a felette levő kettő összegeként. Egy hasonló eljárással felírható a Fibonacci háromszög is. Minden egyes elemet kiszámíthatunk a felette levő két elem segítségével. 2.ábra - A 4. sor elemei segítségével kiszámítható az 5. sor
Az elemeket az 5. sorban úgy kapjuk meg, hogy az ábrán látható módon vesszük a két felső elemet, azokat külön megszorozzuk egy megfelelő Fibonacci számmal majd összeadjuk őket. Ez természetesen nem érvényes a két széllső elemre. Ezt a módszert D. E. Knuth adta meg a A Számítógép-programozás Művészete [5] című könyvények első kötetében. Az általa megadott képlet a következő:
10
III. A Fibonomiális Fraktálok vizsgálatának módszerei
III. 1. Két módszer a Fibonomiális tábla felírására A fraktálok rajzolásához fel kell építenünk a Fibonomiális táblát. Meg kell vizsgálnunk ennek módszereit. Általános képlet alapján kiszámíthatjuk a tábla elemeit, azonban bevezetünk egy új fogalmat, amely merőben hasonlít a binomiális formulára. Fel kell ismernünk a tényt, hogy, bár számítógépünk gyorsan számol, mégis az elméletben egyszerű módszerek nem alkalmasak arra, hogy megfelelő idő alatt kirajzoljunk velük fraktálokat. Több Fibonacci szám-tesztet végeztünk el. Kiderült, mint későbbiekben is látni fogjuk, hogy az adott számokkal való műveletek nagyon nagy számokat eredményeznek, annál is inkább, mivel szoroznunk is kell őket. A Fibonacci sorozat pedig elég gyorsan növekszik. Lényegében a sorozat hatványainak együtthatóival kell dolgoznunk. Az első öt hatványt könnyedén megkaphattuk, de nekunk több százra van szükségünk. Ezért a több módszert eggyé kell forrasztanunk és gyakorlatba ültetnünk.
III. 1. 1. Fibonacci faktoriális A faktoriális fogalma ismert szintén középiskolából, annál is inkább, mivel a kombinációk kiszámításához használatos. A faktoriális n szám szorzatát jelenti, ahol a számok n-től 1-ig tartanak, és nem ismétlődnek, azaz 1-től n-ig a számok szorzatát jelenti. E szorzat helyett értelmezhetjük a Fibonacci számok szorzatát, ezáltal a Fibonacci faktoriálist, másként Fibonomiális faktort, ahol a tényezők az adott számok. Ezen faktor jelölésére az n!F-t használják általában, azonban az F!n sokkalta használhatóbb és talán érthetőbb, ezért mi ezt használjuk a továbbiakban. Általános képlete a következő:
11
A Fibonacci faktoriális nagyon gyorsan növekszik, láthatjuk, hogy míg az
, az
már nagy szám: 122522400 és a 20-dik, már 9692987370815489224102512784450560000 amelyet „normális” körülmények között nem lehet a számítógép memóriájában tárolni. Ezért nehezíti meg a fraktál kirajzolásának műveletét. Létezik azonban több módszer is a nagy számok tárolására. Meg kell jegyeznünk, hogy az általunk használt Fibonacci sorban a zéródik elem 1, így a mi esetünkben értelmezve van a faktoriális. Azonban vannak olyan szakirodalmak, amelyek szerint a nulladik Fibonacci szám a 0. Ez esetben értelmetlen falktoriálist számolni, hisz az eredmény mindig nulla. Vigyáznunk kell arra is, hogy egyes implementációkban a mátrix-szorzással számolt Fibonacci számok esetében is a nulladik elem valóban 0 lesz.
III. 1. 2. Fibonomiális formula Most egy új formát vezetünk be a binomiális együtthatók jelölésére, amely egyben a Fibonomiális együtthatókat fogja eredményezni. A jelölés annyiban különbözik a binomiális együtthatók jelölésétől, hogy egy F indexel jelöljük, hogy Fibonomiális együtthatót számítunk. A képlet hasonlatos a kombináció képletére, azonban itt a természetes faktoriális helyett a már általunk említett Fibonacci faktoriálisokat használjuk.
tagok leegyszerűsödek, hisz a
A kifejtés után látszik, hogy az
számlálóban és a nevezőben is egyaránt előfordulnak. Nincs általános elv a Fibonomiális együtthatók jelölésére. D. Knuth és sokan mások dubpla zárójeleket használnak:
.
Ezzel a módszerrel könnyen felírható a Fibonomiális tábla, elméletileg. Azonban a gyakorlatban a faktoriális számítás miatt az algoritmusunk nem a leggyorsabb, nem beszélve a a memóriaigényről, és arról, hogy egyszerű egész tipusú változókkal nem sokáig jutunk el, még akkor sem ha 64 biten ábrázoljuk őket.
12
A számításhoz és a tábla tárolásához mátrixot használunk. Ennek n sora és k oszlopa van, úgy hogy
- ig megy. Vagyis az eslő sorban a 0-tól
és minden sorban az index
nulláig, az utolsóban 0-tól n-ig . Így a gyakorlatilag a mátrix főátlója alatti részt használjuk a főátlóval és a fölötte levő átlóval együtt. A főátló feletti átlót manuálisan 1-esekkel töltjük ki, mivel a
, és ezesetben megszegné ezt a kikötést.
2.táblázat A Fibonomiális tábla, ahogyan egy számítógép memóriájában tárolnánk Sor és k
oszlop indexek
n
0
1
2
3
4
5
6
1
1
1
2
1
1
1
3
1
2
2
1
4
1
3
6
3
1
5
1
5
15
15
5
1
6
1
8
40
60
40
8
1
7
1
13
104
260
260
104
13
7
1
Ha ebben a mátrixban páronként megszorozzuk az oszlopokat -1 –el, akkor egyenesen a Fibonomiális táblához jutunk. Láttuk tehát, hogy ugyanúgy ahogy a Pascal háromszög esetében, itt is megkaphatóak az együtthatók.
13
III. 1. 3. Általános formula A tábla elemeinek felírására ismert egy általános képlet:
Ezzel direkt módon meghatározhatóak az elemek. Például:
Egy fontos összefüggés felfedése után egyszerűbb felírni a tábla elemeit. A fenti általános formula is ennek az összefüggésnek az általánosítása. Minden elem az előző kettő átlós szorzatából épül fel. A következő ábrán látható hogyan szorzódnak össze a Fibonacci törtek, melyek a következőképpen épülnek fel, az előző elemek segítségével: 2.ábra – Fibonomiális tábla. A körökben az összeszorzandó törtek láthatók
14
Minden Fibonacci törtel az átlón, sorról sorra haladva kapjuk az elemeket, ezeket összekombinálva kaptuk meg a fenti általános formulát. Az optimális módszer nem áll messze ettől, sőt az átalános elv nélkül nem is állna fenn, azonban kicsit más megközelítést igényel. Kimutatható az is, hogy a Lucas számok szintén megjelennek a Fibonacci törtekben. A Lucas számok, amelyek hasonló rekurzív formulát követnek, a következőképpen vannak mehatározva:
A
sor felének meghatározására használt Fibonacci tört Lucas szám. Tény, hogy a sor középső eleme, a
-dik átlóban van. Az erre felírható Fibonacci tört:
Ezt leegyszerűsítve, a k-adik Lucas számot kapjuk.
15
III. 2. A fibonomiális fraktálok rajzolása
A fraktálok megrajzolásának algoritmusa elemi, azonban a futásidejét tekintve nagyon lassú. A Fibonomiális tábla elemei rendkívűl gyorsan növekszenek. A számítógépen való tárolásuk nem egy egyszerű feladat és a velük végzett számítások igen sok ideig eltarthatnak. A Java környezet szolgáltat számunkra olyan egész és lebegőpontos típust, mely megengedi hatalmas egész és valósz számok tárolását. Az algoritmus ezáltal sokat veszít hatékonyságából, azonban ezek a típusok lehetővé teszik, hogy eltároljuk a fibonomiális táblát. A kirajzolt fraktálszerű kép az elemek egy számmal való osztási maradékaira épül. Tehát felmerül a kérdés, hogy van-e lehetőség csak a maradékokkal számolni. Sajnos nincs, mivel bejön a számításokba a 0 szorzó és osztó, amelyek összezavarják a végeredményt.
III. 2. 1. A tábla elemeinek kiszámítása A táblát szükséges eltárolnunk, mivel minden elemet az előző elemek segítségével számítunk ki. Erre a az előző részben említett módszert használjuk. Viszont van egy annyi előnyünk, hogy minden előző sorban már számoltunk. Ezért csak az előző két sor elemeit fogjuk felhasználni a számításokhoz, nincs szükség átló mentén vegigszorozni minden törtet, amit a (2) ábra is szemléltet. Erre hamar rájöhetünk, ha vetünk néhány pillantást az említett ábrára. A Java programozási nyelvbe implementáltak egy BigInteger és egy BigDecimal nevű osztályt. Segítségükkel nagy méretű egész és valós számok tárolhatók és végezhető velük minden aritmetikai művelet. A táblát tehát egy BigInteger típusú mátrixban fogjuk tárolni. A mai számítógépeken nem probléma a memória méret, a számunkra szükséges mennyiség garantáltan megvan minden gépben. Azonban szükséges számítások már komolyabb kihívás elé állítják a számítógép mikroprocesszorát.
16
Első lépésként feltöltjük az első oszlopot és a főátlót 1-esekkel, majd a második oszlopot a Fibonacci számokkal égész n-ig (n a táblázat magassága). Majd elkezdjük kiszámolni a már feltöltött elemeke segítségével a tábla üresen maradt részébe eső elemeit. Mikor ez elkészült, elvégezzük a maradékos osztást. Az elemeket rendre a következőképpen kapjuk meg:
Ebben az esetben a már kiszámolt értékekre támaszkodva határoztuk meg az új elemeket, így csökkentettük az algoritmus futási idejét. Ha az első módszert használtuk volna, akkor rengeteg időt felemésztett volna a faktoriálisok számítása. A második esetben, hasznos ugyan a képlet, de itt előre, külön ki kell generálnunk a Fibonacci számokat, nem beszélve arról, hogy hatványoznunk kell a -1 –et és a Fibonacci törtek szorzatát is meg kell határoznuk. Nem használtuk a D. E. Knuth által megadott képletet sem, amely a Binomiális együtthatók című résznél került említésre, mivel ott minden esetben két Fibonacci számot kellett volna meghatároznunk. Ekkora számok esetén még, ha mátrix-szorzással határoznánk meg a Fibonacci számokat, akkor is sok erőforrást felemésztene. Bármennyire is törekszünk az optimális megoldás megtalálására, a számítások időbe telnek. A promunkba beépítünk egy a számítás állapotát jelző sávot. A teszt futtatások során látható volt, hogyan növekedik a számítási idő. Ezt jól szemléltette a folyamat/állapotkijelző. A BigDecimal osztályt használva egy ideiglenes változóban tároltuk az osztás eredményét, majd ezt szoroztuk a megfelelő elemmel. Annak függvényében, hogy a BigDecimal típusú változónk scale tulajdonságát mekkorára állítjuk, kapunk reális képet. Egy átlagos 200-as méretű scale-el és 100 magassággal a fraktálunk belső része nem lesz megfelelően kiszámítva. Egy bizonyos sor után már nem férnek el a nagy számaink a BigDecimal adott preciziós példányában. Ezt láthatjuk a programban is.
17
III. 3. 2. A fraktálok rajzolása Miután elkészűlt a számítás, már csak ki kell rajzolnunk a fraktált. Két színt használtunk, egy színt a zéró maradékoknak és egy másikat a többi maradéknak. A kirajzolás nem nagy feladat. A mátrixunk főátló alatti részéből kiteszünk egy-egy kisméretű alakzatot a megfelelő színben. Annyi a dolgunk, hogy a mátrix csúcsát középre helyezzük, és következő elemeket alá háromszög alakba rendezzük el. Ennek megvalósítására az X és Y koordinátákat a következőképpen számítjuk ki: new Point((panel2.get_Width()/2 - (i*4) / 2) + j*4, i*4 + 10);
A Point osztály konstruktorának két paramétere van, x és y. Az első az x, amelyet úgy számolunk ki, hogy a panelünk széllességének feléből kivontuk a sor számának felét, így megkapva, hogy honnan kezdődik a sor és ehhez hozáadtunk egy j oszlopnyi eltolást. A az y pedig mindig az aktuális sor. Használtunk még módosítókat, hogy esztétikusabb legyen az elrendezés. Tehát a rajzolás lényegében a feladat legegyszerűbb része volt. A számolási lépes az ami megadja a fraktálunkat. És az is amely az eredeti kérdés elé állított minket.
18
IV. Eredmények
A feladat egyszerű volt, viszont annál nehezebb az út, amíg eljutottunk az eredményekig. Feltételeztük, hogy a Sierpinski fraktálhoz hasonló fraktált rajzolhatunk a Fibonomiális táblából. A feladat az volt, hogy rajzoljuk is meg. Az eredmények pedig ezek a kirajzolt fraktálok. Láttunk a rajzolás mögött relytőző matematikát és Fibonomiális tábla tulajdonságait, azt, hogyan számíthatjuk ki a tábla elemeit matematikailag és számítógép segítségével, és hogyan kaphatunk egy általános képletet, ami segít viszonylag egyszerű számításokkal felépíteni a táblát. Lássunk most néhány Fibonomiális Fraktált: 3.ábra – A hárommal való osztási maradék alapján készült fraktál
Ezen kép elkészítéséhez ( 3.ábra ) számítások 9.98 másodpercig tartottak. Ez a fraktál kicsi méretű és mégis nem egészen tíz másodpercig tartott a számolás. A táblázatban szereplő elemek számjegyeinek száma meghaladja a 15-öt. A következő ábrán ( 4.ábra ) pedig láthatóak alacsony precizióval számolt BigDecimal számok. Itt egy adott sor után már összezavarodnak a számok és nem a megfelelő fraktált eredményezik. Ha nagyobb fraktált szeretnénk rajzolni, nagyobb preciziót kell megadnunk. Ez természetesen nagyobb munkaidőt igényel a számítógéptől. Egy igazán nagy 1000 magasságú fraktál rajzolásához közel egy órára van szükség.
19
4.ábra – A hibás számítások után kapott fraktál
Ezután lássuk a többi maradékok alapján kirajzolt fraktálokat: 5.ábra – A néggyel és öttel való osztás esetén kirajzolt fraktálok
6.ábra – Hattal és héttel való osztás esetén kirajzolt fraktálok
20
7.ábra – Nyolcal és kilenccel való osztás esetén kirajzolt fraktálok
IV. 1. Fraktálok a Pascal-háromszögből A
Pascal-háromszögből
szintén
felépíthetünk
a
Fibonacci
fraktálokhoz
hasonló
környezeteket. Nevezzük a továbbiakban ezeket binomiális-fraktáloknak, míg a fent bemutatott ábrákat fibonomiális-fraktáloknak. A binomiális-fraktálok néhány osztóra megegyeznek a fibonomiális társaikkal, és sok más osztóra hasonló képet adnak, míg általában nem prím számok esetén teljesen más ábrákat eredményeznek. A Pascal-háromszög elemei hasonló oszthatósági tulajdonásgokkal rendelkeznek a Fibonomiális tábla elemeihez hasonlóan, ezért is eredményeznek hasonló ábrákat. Az osztási maradékokat több színnel is színezhetjük. Az osztható tartományokat fehérre, az 1 maradékosztályokat vörösre, a 2 maradékosztályokat zöldre a többit mind narancssárgára. Akár több színt is megadhatunk, de mindig annyit érmemes megadni, aháyn különböző maradékosztályunk van. Ez természetesen megegyezik magával az osztóval. A következő ábrákon láthatunk több színnel rajzolt fibonomiális- és binomiális fraktálokat. Itt látható, hogy a színek nem mutatnak olyan rendezettséget, mint, maguk a két színnel ábrázolt fraktálok.
21
8.ábra – Hárommal való osztás esetén kirajzolt Pascal-fraktál
9.ábra – A néggyel való oszthatóság több színnel rajzolva, Bal oldalon a Fibonacci- míg jobb oldalon a Pascal-fraktál
22
IV. 2. Összehasonlítás Mint láthattuk, a prímszámokkal való osztás esetén nagyon hasonló vagy megegyező ábrákat kapunk a fibonomiális- illetve a binomiális-fraktálokból. Az 2,5,7 prímszámok esetén ugyanazt a fraktált nyerjük. A 3-al való osztás esetén majdnem teljesen azonos az ábra, viszont a Fibonomiális tábla esetén a fehér oszthatósági háromszögek később növekednek. 10.ábra – A 3-al való oszthatóság: bal oldalon a Fibonomiális táblából rajzolt fraktál, jobb oldalon a binomiális-fraktál.
A képek csak abban az esetben egyeznek meg, ha két színt használunk. Ha több szint használunk, az oszthatósági, fehér tartományokon kívül eső elemek nem egyeznek meg. Ez értelemszerű, mivel, ha az elemek ugyanúgy lennének oszthatóak, akkor azt mondhatnánk, hogy a Fibonomiális tábla elemei rendre a Pascal háromszög elemeinek többszörösei, de ez természetesen nem igaz ebben a formában. Láttuk már, hogy milyen összefüggések állnak fenn a két tábla között, azonban ezek, tudomásom szerint nem írhatók fel direkt módon a táblák elemei között.
23
11.ábra – A 7-el való oszthatóság. Láthatóak a különbségek. Bal oldalon a fibonomiális- jobb oldalon a binomiális fraktálok
24
Könyvészet [1] Bege Antal, Kása Zoltán: Algoritmikus kombinatorika és számelmélet, Presa. Univ. Clujeană, Cluj-Napoca, 2006
[2] William B. Everett: Number Of Binomial Coefficients divisible by a fixed power of a prime, Integers: Electronic Journal of Combinatorial number theory, 8 (2008), A11 [3] Sergio Falcón, Angél Plaza: The k-Fibonacci sequence and the Pascal 2-triangle. Chaos, Solitons and Fractals 33 (2007), 38 - 49 [4] Dale K. Hathaway and Stephen L. Brown: Fibonacci Powers and a Fascinating Triangle. The College Mathematics Journal, 28 (1997), 124 - 128 [5] Donald E. Knuth: A számítógép-programozás művészete, 1. Alapvető algoritmusok, Műszaki Könyvkiadó, Budapest , 1987 [6] David Zeitlin and F. D. Parker: FQ H-14, The Fibonacci Quarterly, 2 (1963), 54
25
