Fibonaccijev brojevni sustav
Sažetak
U ovom članku prikazujemo kako pomoću Fibonaccijevih brojeva izgraditi brojevni sustav.1Uvod
Najveći matematičar srednjeg vijeka, Leonardo iz Pise, poznatiji kao Fibonacci, otkrio je neobičan matematički niz koji danas nosi njegovo ime. Fibonaccijev niz čine brojevi 1,1,2,3,5,8,13,21,… pri čemu se svaki sljedeći broj računa kao zbroj prethodnih dvaju u nizu. Elementi Fibonaccijeva niza nazivaju se i Fibonaccijevi brojevi. Fibonacci je do tog otkrića došao promatrajući razmnožavanje zečeva u prirodi, te pokušavajući predvidjeti koliko će parova zečića podignuti jedan par zečjih roditelja u jednoj godini. Očito, navedeni niz možemo definirati i rekurzivnom relacijom Fn=Fn−1+Fn−2,F1=1,F2=1.
Zanimljivu primjenu Fibonaccijevih brojeva nalazimo pri njihovu korištenju kao baze za prikazivanje prirodnih brojeva. U toj se bazi prirodni brojevi prikazuju kao sume nekoliko Fibonaccijevih brojeva, no postoje određene prepreke koje najprije valja ukloniti kako bi prikaz bio jedinstven.
Fibonaccijev brojevni sustav povezuje razne grane matematike, kao što su kombinatorika i teorija brojeva, s određenim dijelovima teorijskog računarstva poput kriptografije i algoritama za pretraživanje podataka. U računarstvu se osobito pokazao korisnim za sustave u kojima se podaci serijski pohranjuju i traže
2Fibonaccijev brojevni sustav
U matematici se za prikaz prirodnih brojeva koriste različiti brojevni sustavi. Najpoznatiji su binarni i dekadski. U binarnom sustavu prirodne brojeve prikazujemo kao sumu potencija broja 2 koje množimo znamenkama 0 i 1, dok u dekadskom brojeve prikazujemo kao sumu potencija broja 10 koje množimo znamenkama 0,1,2,3,4,5,6,7,8 i 9.
Fibonaccijev brojevni sustav je onaj u kojem brojeve prikazujemo kao sumu Fibonaccijevih brojeva. Dakle, neki prirodni broj N možemo prikazati kao N=an−1Fn+1+…+a2F4+a1F3+a0F2, gdje je su Fi brojevi Fibonaccijeva niza koji zadovoljavaju relaciju Fi=Fi−1+Fi−2,F2=1=F2, te je ai∈{0,1}. Ovaj sustav sličan je binarnom brojevnom sustavu, jer se koristi samo znamenkama 0 i 1, ali za razliku od binarnog brojevnog sustava, čija je baza broj 2, u ovom sustavu baza su Fibonaccijevi brojevi.
Primjer 1.Prikažimo broj 8 u Fibonaccijevu brojevnom sustavu.
8=F6=F5+F4=F5+F3+F2=F5+F3+F1
Kao što vidimo, broj 8 možemo prikazati na nekoliko načina s pomoću Fibonaccijevih brojeva. Bolji pregled daje nam sljedeća tablica. Fi | F6 | F5 | F4 | F3 | F2 | F1 |
Vrijednost | 8 | 5 | 4 | 3 | 2 | 1 |
ai | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 0 | |
0 | 1 | 0 | 1 | 1 | 0 | |
0 | 1 | 0 | 1 | 0 | 1 |
Za prikaz broja 8 u Fibonaccijevoj bazi uzeli smo četiri Fibonaccijeva broja, a pojavilo se nekoliko prikaza. To nam govori da za prirodne brojeve u Fibonaccijevoj bazi nećemo dobiti jedinstven prikaz broja jer postoji više od jednog načina kako bismo prikazali taj broj. Kako možemo urediti novi brojevni sustav u kojem će prikazi prirodnih brojeva biti jedinstveni?
Do nejedinstvenosti dolazi zbog dva razloga:
(1) | F2=F1=1 Ovaj problem rješavamo tako da odlučimo koji ćemo od ta dva broja upotrijebiti u prikazu. |
(2) | Fi=Fi−1+Fi−2 U prikazu možemo izabrati Fi ili Fi−1+Fi−2. Na ovaj način dobivamo najkraći ili najdulji mogući prikaz. Prirodno je odabrati najkraći prikaz. |
Teorem 2. (Zeckendorf)Svaki prirodan broj N može se prikazati kao zbroj različitih Fibonaccijevih brojeva
N=Fi1+Fi2+…+Fir
tako da je pritom ik+1≤ik−2 za k=1,2,…,r−1 te je ir≥2.
Dokaz.Dokaz teorema provodimo matematičkom indukcijom. Za N=1 tvrdnja je točna jer je F2=1. Pretpostavimo da je N≥2 prirodan broj te da je tvrdnja točna za sve brojeve manje od N. Sada preostaje dokazati korak indukcije. Odaberimo n∈N tako da je Fn≤N<Fn+1. Ako je N=Fn, tada je tvrdnja točna. Pretpostavimo da je N>Fn. Očito je N−Fn<N, pa na broj N−Fn možemo primijeniti pretpostavku indukcije te dobivamo N−Fn=Fi1+…+Fir. Odatle je N=Fn+(N−Fn)=Fn+Fi1+…+Fir te još treba provjeriti da je i1≤n−2.
Ova tvrdnja slijedi direktno iz Fi1≤N−Fn<Fn+1−Fn=Fn−1.
Ova tvrdnja slijedi direktno iz Fi1≤N−Fn<Fn+1−Fn=Fn−1.
◼
Edouard Zeckendorf, belgijski zaljubljenik u matematiku, izveo je svoj teorem 1939. Otprilike 20 godina poslije, David E. Daykin pokazao je u vrlo netrivijalnom radu
Teorem 3. (Lekkerkerker)Kanonski prikaz je jedinstven.
Dokaz. Dokaz se ponovno provodi matematičkom indukcijom. Kao i u prethodnom teoremu, neka je N≥2 te pretpostavimo da svi brojevi manji od N imaju jedinstven prikaz. Dokažimo sad korak indukcije. Odaberimo n∈N tako da je Fn≤N<Fn+1. Dokazat ćemo da se u kanonskom prikazu broja N mora pojaviti broj Fn.
Kada se Fn ne bi pojavio kanonskom prikazu, imali bismo Fi1≤Fn−1,Fi2≤Fn−3,… Ako je n paran, zapišimo ga u obliku n=2i, te dobivamo N≤F2i−1+F2i−3+…+F3=F2i−F2=Fn−1. Slično, ako je n neparan, možemo ga zapisati u obliku n=2i+1, te dobivamo N≤F2i+F2i−2+…+F2=F2i+1−F1=Fn−1. U oba slučaja dobili smo kontradikciju, pa slijedi da Fn mora biti dio kanonskog prikaza prirodnog broja N.
Dakle, broj N prikazali smo kao N=Fn+m. Zašto nam pojavljivanje broja Fn garantira jedinstvenost prikaza? Pretpostavimo da postoje dva različita prikaza broja N. Tada bi postojala i dva različita prikaza od m, što je u kontradikciji s pretpostavkom indukcije, jer je m<N.
Kada se Fn ne bi pojavio kanonskom prikazu, imali bismo Fi1≤Fn−1,Fi2≤Fn−3,… Ako je n paran, zapišimo ga u obliku n=2i, te dobivamo N≤F2i−1+F2i−3+…+F3=F2i−F2=Fn−1. Slično, ako je n neparan, možemo ga zapisati u obliku n=2i+1, te dobivamo N≤F2i+F2i−2+…+F2=F2i+1−F1=Fn−1. U oba slučaja dobili smo kontradikciju, pa slijedi da Fn mora biti dio kanonskog prikaza prirodnog broja N.
Dakle, broj N prikazali smo kao N=Fn+m. Zašto nam pojavljivanje broja Fn garantira jedinstvenost prikaza? Pretpostavimo da postoje dva različita prikaza broja N. Tada bi postojala i dva različita prikaza od m, što je u kontradikciji s pretpostavkom indukcije, jer je m<N.
◼
Dakle, broj 8 iz našeg primjera na jedinstven način u Fibonaccijevu sustavu prikazujemo kao 8=F6=1F6+0F5+0F4+0F3+0F2=1000Fib.
Algoritam
Iz prethodnih dvaju teorema proizlazi jednostavan algoritam za pronalaženje kanonskog prikaza broja prirodnog broja N:
i1=max{i∈N:Fi≤N},
i2=max{i∈N:Fi≤N−Fi1},
i3=max{i∈N:Fi≤N−Fi1−Fi2},
⋮
Zadatak 4.Koristeći se gornjim algoritamom prikažite prirodne brojeve 16,33 i 57 u kanonskom prikazu Fibonaccijeva sustava.
3Fibonaccijevi kodovi
Fibonaccijev brojevni sustav od velike je važnosti za kriptografiju jer prirodne brojeve prikazane u Fibonaccijevu sustavu možemo na jednostavan način pretvoriti u kodove. Fibonaccijevi kodovi atraktivniji su u odnosu na ostale univerzalne kodove, jer omogućuju lako određivanje polaznih podataka i jednostavnu, zahvalnu manipulaciju. Zbog tog zanimljivog svojstva, Fibonaccijevi kodovi često nalaze svoju primjenu u programiranju i analizi tržišta kapitala.
U binarnom sustavu svaki niz znamenki 0 i 1 predstavlja neki broj. Pogreška bilo koje vrste, poput nedostatka neke znamenke, opet daje valjani prikaz nekog drugog broja, stoga lako može proći neopaženo. Fibonaccijev sustav pretvara brojeve u nizove znamenki nula i jedinica, u kojem se nikada dvije jednice ne mogu pojaviti zajedno u slijedu. Kada je god 0 koja slijedi ili prethodi 1, slučajno zamijenjena s 1, takva se pogreška lako uočava. Ovo svojstvo Fibonaccijeva sustava daje Fibonaccijevu kodu veliku prednost u odnosu na druge postojeće kodove. Oštećeni niz podataka ne postaje beskoristan, nego se tijekom procesa dekodiranja gube najviše tri znamenke.
Pogledajmo kako na jednostavan način možemo dobiti Fibonaccijeve kodove:
Prikažimo broj 18 u Fibonaccijevoj bazi: 18=13+5=F7+F5=1F7+0F6+1F5+0F4+0F3+0F2=101000Fib. Fibonaccijev kod za prirodan broj N definira se kao Fib(N)=a0a1a2…an−1 gdje su a0,a1,…,an−1 znamenke u prikazu prirodnog broja N=an−1Fn+1+…+a2F4+a1F3+a0F2 u Fibonaccijevoj bazi. Fibonaccijev kod je obratan od uobičajenog zapisa brojeva u bazi, u kojem je krajnja lijeva znamenka ona koja u prikazu broja stoji uz najveću potenciju baze. U našem slučaju, uz najveći Fibonaccijev broj. Dakle, ako je 101000Fib prikaz broja 18 u Fibonaccijevoj bazi, tada je Fibonaccijev kod tog broja Fib(18)=000101.
Na isti način prikažimo brojeve 33 i 6: 33=21+8+3+1=1F8+0F7+1F6+0F5+1F4+0F3+1F2=1010101Fib6=5+1=1F5+0F4+0F3+1F2=1001Fib Dobivamo Fib(33)=1010101 i Fib(6)=1001.
Kada bismo dane brojeve zapisali u binarnoj bazi, dobili bismo također niz nula i jedinica koje predstavljaju binarnu inačicu broja. Pogledajmo kako tada zapis glasi:
33=100012
18=010012
6=0112.
18=010012
6=0112.
Napravimo li redom konkatenaciju brojeva 33, 18 i 6 zapisanih u binarnom sustavu (tj. zapišemo li odgovarajuće binarne prikaze jednog za drugim), dobivamo niz nula i jedinica 1000101001011. Budući da smo unaprijed zadali brojeve, znamo od kojih je brojeva ovaj niz sastavljen. Međutim, ako bismo pred sobom imali isti niz nula i jedinica 1000101001011 bez prethodnog saznanja od kojih brojeva je on sastavljen, ne bismo ga znali dešifrirati, jer ne bismo znali gdje jedan broj počinje ili završava.
Na isti problem naišli bismo kada bismo napravili konkatenaciju Fibonaccijevih kodova za prirodne brojeve 33, 18 i 6, odnosno Fib(33)Fib(18)Fib(6). Dobili bismo niz nula i jedinica 10101010001011001. Međutim, kod brojeva u Fibonaccijevu brojevnom sustavu taj problem možemo lako riješiti. U zapisu svakog koda, iza zadnje znamenke stavimo dodatnu jedinicu:
Fib(33)=10101011
Fib(18)=0001011
Fib(6)=10011
Fib(18)=0001011
Fib(6)=10011
Sada lako možemo odrediti gdje neki broj počinje, a drugi završava. Kad god naiđemo na dvije susjedne jedinice, znamo da smo došli na kraj niza koji prikazuje određeni broj. Moramo voditi računa o tome da imamo jednu jedinicu viška koja nam služi isključivo za odvajanje i ne koristi se pri pretvorbi u polazni broj. Zeckendorfov teorem osigurava nam nepostojanje susjednih jedinica u zapisu prirodnog broja u Fibonaccijevoj bazi te je ovo dodavanje jedinice moguće.
Napravimo sada konkatenaciju brojeva u Fibonaccijevoj bazi čijem smo zapisu dodali jedinicu Fib(33)Fib(18)Fib(6)=10101011000101110011. Jednostavnim rastavom možemo pronaći brojeve koji izgrađuju dani niz nula i jedinica 33⏞1010101_1_18⏞000101_1_6⏞1001_1_
Zadatak 5.Odredite prirodne brojeve čiji se Fibonaccijev kod nalazi u nizu 1001010011100011101011.
4Proširenja Fibonaccijeva sustava
Fibonaccijev brojevni sustav može se na jednostavan način proširiti do drugih brojevnih sustava, u kojima prirodne brojeve prikazujemo kao sume takozvanih proširenih Fibonaccijevih brojeva. Neki od predstavnika tih sustava su tribonaccijev brojevni sustav, zatim brojevni sustav koji je definirao S. T. Klein
4.1Tribonaccijev brojevni sustav
Proširivanjem Fibonaccijevih brojeva dobivamo tribonaccijeve brojeve koji su definirani rekurzijom Fi=Fi−1+Fi−2+Fi−3 uz uvjet F3=2,F2=1,F1=1. Dok se svaki sljedeći Fibonaccijev broj dobiva zbrajanjem prethodnih dvaju, svaki tribonaccijev broj dobivamo zbrajanjem prethodnih triju, pa su 1,1,2,4,7,13,24,44,81,149… neki od prvih članova tribonaccijeva niza.
Na prirodan način možemo proširiti Fibonaccijev brojevni sustav do tribonaccijeva brojevnog sustava. U ovom sustavu prirodan broj N može se prikazati kao N=an−1Fn+1+…+a2F4+a1F3+a0F2, gdje je Fi=Fi−1+Fi−2+Fi−3,F4=22,F3=21,F2=20. U tribonaccijevu sustavu prirodne brojeve također možemo prikazati na više načina. A. S. Fraenkel pokazao je 1985.
Pogledamo li odgovarajući zapis broja 7, imamo dvije mogućnosti:
(1)
7=F5=1F5+0F4+0F3+0F2
(2)
7=4+2+1=0F5+1F4+1F3+1F2.
Zadatak 6.Prirodne brojeve 4, 8 i 14 zapišite u tribonaccijevu brojevnom sustavu.
4.2Brojevni sustav srodan Fibonaccijevom
Drugo proširenje Fibonaccijeva sustava je brojevni sustav koji je definirao S. T. Klein, u kojem prirodne brojeve prikazujemo u obliku N=an−1Fn+1+…+a2F4+a1F3+a0F2 gdje je Fi=Fi−1+Fi−m,zai>m+1 Fi=i−1,za1≤i≤m+1,uz uvjetm≥2. Kao i prethodni sustavi, ovaj sustav u sebi također sadržava višestruke prikaze. Jedinstvenost u prikazu prirodnog broja kao n-torke koja se sastoji od nula i jedinica možemo postići uz uvjet da se između svakog para jedinica nalazi najmanje m−1 nula
Za m=2, ovaj sustav odgovara Fibonaccijevu sustavu. Promotrimo slučaj m=3. Baza je tada definirana s Fi=Fi−1+Fi−3 te F4=3,F3=2 i F2=1. Primjerice, prvih pet prirodnih brojeva u novoj bazi možemo prikazati kao N=a3F5+a2F4+a1F3+a0F2, tj. N=a34+a23+a12+a0. Zbog gore navedenog uvjeta, odbacujemo one prikaze u kojima se između jedinica pojavljuje manje od m−1 nula. U sljedećoj tablici označili smo prikaze koje odbacujemo jer ne zadovoljavaju traženo svojstvo.
a3 | a2 | a1 | a0 | N | |
0 | 0 | 0 | 1 | 1 | |
0 | 0 | 1 | 0 | 2 | |
0 | 0 | 1 | 1 | 3 | ← odbacujemo |
0 | 1 | 0 | 0 | 3 | |
0 | 1 | 0 | 1 | 4 | ← odbacujemo |
1 | 0 | 0 | 0 | 4 | |
0 | 1 | 1 | 0 | 5 | ← odbacujemo |
1 | 0 | 0 | 1 | 5 |
4.3m-naccijev brojevni sustav
Pogledajmo ukratko i treće proširenje Fibonaccijeva brojevnog sustava, poznato pod nazivom m-naccijev brojevni sustav. Prirodan broj u ovom sustavu možemo prikazati kao N=an−1Fn+1+…+a2F4+a1F3+a0F2,
gdje je baza dana s Fi=mFi−1−Fi−2,zai>3iF3=m,F2=1, a znamenke ai s 0,1,2,…,m−1 za m≥3. Prethodna tri sustava imala su samo dvije znamenke, 0 i 1, dok m–naccijev sustav ima onoliko znamenki koliki m odaberemo, uz uvjet da je m barem 3. Odaberemo li m=3, dobivamo m–naccijev brojevni sustav s tri znamenke 0,1,2. Broj 5 u takvom sustavu možemo prikazati u obliku 5=3+2=F3+2F2 tj. 5=12m3.
Budući da i u ovom brojevnom sustavu postoji više mogućnosti za prikaz prirodnih brojeva, jedinstvenost možemo postići uz neke restrikcije. U radu
Zapišemo li u m-naccijevu sustavu s tri znamenke broj 8, dobit ćemo dva prikaza
(3)
8=2+6=0F4+2F3+2F2
(4)
8=F4+0F3+0F2.
Zadatak 7. Prirodne brojeve 9, 11 i 17 zapišite u m-naccijevu brojevnom sustavu, gdje je m=3.
Bibliografija
