Hrvatski Fokus
Znanost

Fibonaccijev brojevni sustav

Fibonnacijev niz u prirodi

 
 
Leonardo od Pise (Pisa, oko 1170.– Pisa, oko 1250.), također poznat kao Leonardo Bonacci, Leonardo Fibonacci, ili samo Fibonacci, bio je talijanski matematičar, kojeg su neki uzimali za najtalentiranijeg matematičara srednjeg vijeka. Fibonacci je danas najpoznatiji: po tome što je raširio uporabu arapskih brojaka u Europi.
http://hrvatski-fokus.hr/wp-content/uploads/2019/11/360px-PascalTriangleFibanacci.svg_.png
U matematici, Fibonaccijevi brojevi oblikuju nizdefiniran sljedećom rekurzivnom relacijom:
F ( n ) := { 0 ako je  n = 0 ; 1 ako je  n = 1 ; F n − 1 + F n − 2 ako je  n > 1. {\displaystyle F(n):={\begin{cases}0&{\mbox{ako je }}n=0;\\1&{\mbox{ako je }}n=1;\\F_{n-1}+F_{n-2}\!\,&{\mbox{ako je }}n>1.\\\end{cases}}} To jest, nakon dvije početne vrijedosti, svaki sljedeći broj je zbroj dvaju prethodnika: 2+3 dat će 5, 3+5 dat će 8, 5+8 dat će 13 itd. Prvi Fibonaccijevi brojevi (slijed A000045u OEIS), također označeni kao Fn, za n = 0, 1, … , su:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811…
Ponekad se za ovaj niz smatra da počinje na F1 = 1, ali uobičajenije je uključiti F0 = 0.
Fibonaccijevi brojevi su imenovani po Leonardu od Pise, poznatom kao Fibonacci, iako su ranije opisani u Indiji.
 
Fibonnacijev niz u prirodi
 
Fibonaccijev niz se često povezuje i s brojem zlatnog rezafi (phi, φ), ili brojem kojeg mnogi zovu i "Božanskim omjerom". Uzmemo li jedan dio Fibonaccijevog niza, 2, 3, 5, 8, te podijelimo li svaki sljedeći broj s njemu prethodnim, dobiveni broj težit će broju 1,618 (3/2=1,5; 5/3=1,67; 8/5=1,6; …; 39088169/24157817=1,618034). Broj 1,618 jest broj fi. Odnosi mjera kod biljaka, životinjai ljudi, sa zapanjujućom preciznošću se približava broju fi.
Slijedi nekoliko primjera broja fi i njegove povezanosti sa Fibonaccijem i prirodom:
1.   U pčelinjoj zajednici, košnici, uvijek je manji broj mužjaka pčela nego ženki pčela. Kada bi podijelili broj ženki sa brojem mužjaka pčela, uvijek bi dobili broj fi.
2.   Nautilus (glavonožac), u svojoj konstrukciji ima spirale. Kada bi izračunali odnos svakog spiralnog promjera prema sljedećem dobili bi broj fi.
3.   Sjeme suncokreta raste u suprotnim spiralama. Međusobni odnosi promjera rotacije je broj fi.
4.   Izmjerimo li čovječju dužinu od vrha glave do poda, zatim to podijelimo s dužinom od pupka do poda, dobijamo broj fi.
 
Fibonaccijev brojevni sustav
 
Uvod
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 [1]. Također, prilikom kompresija digitalnih fotografija pokazuje znatne prednosti nad klasičnom LBS metodom koja koristi se binarnim brojevnim sustavom [6]. Osim toga, prikazivanje prirodnih brojeva u Fibonaccijevoj bazi omogućilo je jednostavno kodiranje podataka stvaranjem nizova u kojima se brzo može utvrditi gdje jedan podatak završava, a drugi počinje. Prirodnim proširivanjem Fibonaccijeva brojevnog sustava dobiveni su novi sustavi koji svoju ulogu također pronalaze u računarstvu, jer uz određene uvjete ponovno imaju značajne prednosti kod izvođenja osnovnih aritmetičkih operacija u odnosu na klasični binarni brojevni sustav.

 
Fibonaccijev 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.
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.
Sljedeća dva teorema pokazuju nam kako zaista dobivamo brojevni sustav s jedinstvenim prikazom brojeva ako napravimo ova dva izbora [3].
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∈Ntako da je FnN<Fn+1. Ako je N=Fn, tada je tvrdnja točna. Pretpostavimo da je N>Fn. Očito je NFn<N, pa na broj NFn možemo primijeniti pretpostavku indukcije te dobivamo NFn=Fi1+…+Fir. Odatle je N=Fn+(NFn)=Fn+Fi1+…+Fir te još treba provjeriti da je i1≤n−2.
Ova tvrdnja slijedi direktno iz Fi1≤NFn<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 [2]da je Fibonaccijev niz jedini koji zadovoljava prethodni teorem, odnosno da je Zeckendorfovim teoremom dano definirajuće svojstvo Fibonaccijeva niza. Prikaz prirodnog broja kojim smo se koristili u Zeckendorfovu teoremu nazivamo kanonski prikaz. Idući rezultat pokazuje kako kanonski prikaz prirodnog broja u Fibonaccijevu brojevnom sustavu doista ima traženo svojstvo.
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∈Ntako da je FnN<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 NF2i−1+F2i−3+…+F3=F2iF2=Fn−1. Slično, ako je n neparan, možemo ga zapisati u obliku n=2i+1, te dobivamo

NF2i+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:FiN},
i2=max{i∈N:FiNFi1},
i3=max{i∈N:FiNFi1−Fi2},
Zadatak 4.Koristeći se gornjim algoritamom prikažite prirodne brojeve 16,33 i 57 u kanonskom prikazu Fibonaccijeva sustava.
 
Fibonaccijevi 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:
336=21+8+3+1=1F8+0F7+1F6+0F5+1F4+0F3+1F2=1010101Fib=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
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
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
1010101–331–000101–181–1001–61–
 
Zadatak 5. Odredite prirodne brojeve čiji se Fibonaccijev kod nalazi u nizu 1001010011100011101011
 
Proš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 [5]te direktna generalizacija Fibonacccijeva sustava, koju nazivamo m-bonaccijev brojevni sustav. Ovi brojevni sustavi imaju važnu ulogu u teorijskom računarstvu, gdje se zbog mnogobrojnih zanimljivih svojstava koriste za konačne automate. Mi nećemo proučavati svojstva tih sustava, već ćemo ukratko dati opis prikaza prirodnih brojeva u nekima od tih sustava.
 
Tribonaccijev 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. [4]kako će, ako u prikazu uklonimo grupe u kojima se pojavljuju tri ili više uzastopnih jedinica, prikazi brojeva u tribonaccijevu sustavu biti jedinstveni.
Pogledamo li odgovarajući zapis broja 7, imamo dvije mogućnosti:
(1)
7=F5=1F5+0F4+0F3+0F2
i
(2)
7=4+2+1=0F5+1F4+1F3+1F2.
Odbacujemo onaj zapis u kojem se pojavljuje tri ili više jedinica, odnosno (2). Dobivamo prikaz 7=1000Trib.
Zadatak 6.Prirodne brojeve 4, 8 i 14
zapišite u tribonaccijevu brojevnom sustavu.
 
Brojevni 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+Fim,zai>m+1
Fi=i−1,za1≤im+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 [5].

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.

 
Fibonaccijev 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 [5]je S. T. Klein pokazao kako jedinstvenost prikaza brojeva u m-naccijevom sustavu dobivamo ako se između svakih dvaju pojavljivanja broja m−1 nalazi najmanje jedan i takav da i∈{0,1,…,m−3}.

Zapišemo li u m-naccijevu sustavu s tri znamenke broj 8, dobit ćemo dva prikaza

(3)
8=2+6=0F4+2F3+2F2
i
(4)
8=F4+0F3+0F2.
Prema gornjem uvjetu, odbacujemo prikaz (3) i prihvaćamo (4) kao jedinstveni prikaz broja 8=100m3 u ovoj bazi.
Zadatak 7. Prirodne brojeve 9, 11 i 17 zapišite u m-naccijevu brojevnom sustavu, gdje je m=3.
 

Ljerka Jukić, asistentica Odjela za matematiku Sveučilišta u Osijeku i Helena Velić, studentica Odjela za matematiku Sveučilišta u Osijeku, http://e.math.hr/math_e_article/br16/jukic_velic

Povezane objave

Prevencija iznenadne smrti športaša

HF

Istaknuta hrvatska molekularna biologinja i biokemičarka

HF

Razmišljanje i hodanje

hrvatski-fokus

Zašto neki plodovi podsjećaju na ljudske organe?

HF

Ova web stranica koristi kolačiće za poboljšanje vašeg iskustva. Pretpostavit ćemo da se slažete s tim, ali možete to neprihvatiti i isključiti ukoliko želite. Prihvati Pročitaj više