koliko sam shvatila,tebi je potreban algoritam za izracunavanje tog fibonacijevog broja?
ne znam hoce li ti ovo sta pomoci,nadam se da ces dobiti naku ideju za taj algoritam
u matematici se za izracunavanje n-og fibonacijevog broja koristi metod za resavanje dif. jednacina.stavljajuci f(n)=r^n(r<>0) u rekurzivnu formulu(koju si gore napisao),dobijamo
f(n+2)-f(n+1)-f(n)=r^n(r^2-r-1)=0,pa resavajuci kvadratnu jednacinu dobijamo r=(1+-sqrt(5))/2,pa se uvrstavanjem,za neke konstante A i B dobija
f(n)=A*((1-sqrt(5))/2)^n+B*((1+sqrt(5))/2)^n(ove konstante su potekle od resenja dif. jednacine drugog reda,kojoj polazna rekurzija odgovara)
sada,posto f(n) zadovoljava rekurziju i uzimajuci za n=1 i n=2 dobijamo sistem od dve linearne jednacine po A i B,pa nalazimo da je A=1/sqrt(5) i B=-1/sqrt(5)
zatim imamo
f(n)=(1/sqrt(5))*[((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
kako je drugi clan u zagradi,kad se podeli sa sqrt(5) po aps. vrednosti manji od 1/2,sledi da je f(n) jednak prirodnom broju koji je najblizi prvom clanu u zagradi,kad se podeli sa sqrt(5)
osim toga,vazi tvrdjenje da su za fiksirano k>=3 fibonacijevi brojevi f(m*k)(m=1,2...) deljivi brojem f(k),tj. ostatak je 0,kako se tebi u zadatku trazi
na osnovu ovoga mozes da napravis neki algoritam koji ce ti izracunati broj koji trazis
nesto slicno sam radila u paskalu,pa mislim da nece biti problema
poz

hm !!

ne znam kako je f(n)=(1/sqrt(5))*[((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]

kako je drugi clan u zagradi,kad se podeli sa sqrt(5) po aps. vrednosti manji od 1/2,sledi da je f(n) jednak prirodnom broju koji je najblizi prvom clanu u zagradi,kad se podeli sa sqrt(5)

Sve dobro, ali ja ne dobivam iste rezultate za skalkulirani f(n) i rezultat po toj formuli int (1/sqrt(5))*[((1+sqrt(5))/2)^n/sqrt(5))
n f(n) formula
0 0 1
1 1 2
2 1 3
3 2 6
4 3 9
5 5 16
6 8 25
7 13 42
8 21 67
9 34 110

Gdje je greška ?

((1+sqrt(5))/2)^n
ovo je prvi clan zagrade,njega podeli sa sqrt(5),samo pazi na zagrade i redosled izvrsavanja operacija
dakle
[((1+sqrt(5))/2)^n]/sqrt(5)
kako kvadratna jednacina,u ovom slucaju,ima 2 realna i razlicita resenja,to se f(n),po metodi resavanja dif. jednacina,pise kao zbir ta 2 resenja,koja su,svako ponaosob,pomnozena nekom realnom konstantom
poz

n f(n) I(n)
0 0 0
1 1 0
2 2 1
3 4 1
4 8 3
5 16 4
6 32 8
7 64 12
8 128 21
9 256 33
10 512 55
11 1024 88
12 2048 144
13 4096 232
14 8192 377
15 16384 609
16 32768 987

pri tome je I(n)==INT((((1+SQRT(5))/2)^n)/SQRT(5))

I(n)<>f(n). ne znam kako bi to moglo biti.
Ipak hvala za upute

Neznam, kako bih riješio ovaj primjer, no mislim, da je najbolje da napišem koji program, koji zna da kalkulira i preko 1E300 ili kakvo koju vrstu dedukcije.

On Maple it took half day to get to f(1000000000)
On 16-bit asm it took 1min 42sec to find an answer
On 32-bit asm it toom 28sec to get the answer
On Delphi also 28 sec - checked with disassembler - the code matched with my assembly code.

probat ču sa mod 2^16 i ostalima da vidim dali ima koje veze.

n f(n) mod 32 mod 31 mod 30 mod 29 mod 28 mod 27 mod 26 mod 25
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
3 2 2 2 2 2 2 2 2 2
4 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 5 5
6 8 8 8 8 8 8 8 8 8
7 13 13 13 13 13 13 13 13 13
8 21 21 21 21 21 21 21 21 21
9 34 34 34 34 34 34 34 34 34
10 55 55 55 55 55 55 55 55 55
11 89 89 89 89 89 89 89 89 89
12 144 144 144 144 144 144 144 144 144
13 233 233 233 233 233 233 233 233 233
14 377 377 377 377 377 377 377 377 377
15 610 610 610 610 610 610 610 610 610
16 987 987 987 987 987 987 987 987 987
17 1597 1597 1597 1597 1597 1597 1597 1597 1597
18 2584 2584 2584 2584 2584 2584 2584 2584 2584
19 4181 4181 4181 4181 4181 4181 4181 4181 4181
20 6765 6765 6765 6765 6765 6765 6765 6765 6765
21 10946 10946 10946 10946 10946 10946 10946 10946 10946
22 17711 17711 17711 17711 17711 17711 17711 17711 17711
23 28657 28657 28657 28657 28657 28657 28657 28657 28657
24 46368 46368 46368 46368 46368 46368 46368 46368 46368
25 75025 75025 75025 75025 75025 75025 75025 75025 75025
26 121393 121393 121393 121393 121393 121393 121393 121393 121393
27 196418 196418 196418 196418 196418 196418 196418 196418 196418
28 317811 317811 317811 317811 317811 317811 317811 317811 317811
29 514229 514229 514229 514229 514229 514229 514229 514229 514229
30 832040 832040 832040 832040 832040 832040 832040 832040 832040
31 1346269 1346269 1346269 1346269 1346269 1346269 1346269 1346269 1346269
32 2178309 2178309 2178309 2178309 2178309 2178309 2178309 2178309 2178309
33 3524578 3524578 3524578 3524578 3524578 3524578 3524578 3524578 3524578
34 5702887 5702887 5702887 5702887 5702887 5702887 5702887 5702887 5702887
35 9227465 9227465 9227465 9227465 9227465 9227465 9227465 9227465 9227465
36 14930352 14930352 14930352 14930352 14930352 14930352 14930352 14930352 14930352
37 24157817 24157817 24157817 24157817 24157817 24157817 24157817 24157817 24157817
38 39088169 39088169 39088169 39088169 39088169 39088169 39088169 39088169 5533737
39 63245986 63245986 63245986 63245986 63245986 63245986 63245986 63245986 29691554
40 102334155 102334155 102334155 102334155 102334155 102334155 102334155 35225291 1670859
41 165580141 165580141 165580141 165580141 165580141 165580141 31362413 31362413 31362413
42 267914296 267914296 267914296 267914296 267914296 267914296 133696568 66587704 33033272
43 433494437 433494437 433494437 433494437 433494437 165058981 30841253 30841253 30841253
44 701408733 701408733 701408733 701408733 164537821 164537821 30320093 30320093 30320093
45 1134903170 1134903170 1134903170 61161346 61161346 61161346 61161346 61161346 27606914
46 1836311903 1836311903 1836311903 762570079 225699167 225699167 91481439 24372575 24372575
47 2971215073 2971215073 823731425 823731425 286860513 18425057 18425057 18425057 18425057
48 4807526976 512559680 512559680 512559680 512559680 244124224 109906496 42797632 9243200
49 7778742049 3483774753 1336291105 262549281 262549281 262549281 128331553 61222689 27668257
50 12586269025 3996334433 1848850785 775108961 238238049 238238049 104020321 36911457 3357025
51 20365011074 3185141890 1037658242 1037658242 500787330 232351874 98134146 31025282 31025282
52 32951280099 2886509027 739025379 739025379 202154467 202154467 67936739 827875 827875
53 53316291173 1776683621 1776683621 702941797 166070885 166070885 31853157 31853157 31853157
54 86267571272 368225352 368225352 368225352 368225352 99789896 99789896 32681032 32681032


Odgovor je bolje vidjeti u xls fajlu, ali zbog rounding accurancy u excel-u odgovori nisu baš tačni, tačni su recimo na 12 decimalki.
Sada trebam samo još koji dobar programčič ....

Čini mi se da je za $ F(n) equiv 0 mod 2^{32} $, $n$ jako veliki broj. Zato ti double ne može pomoći, već samo ili program ili procedura koja može da radi sa jako velikim brojevima. Moj ti je savet, ako ne poznaješ problematiku, da uzmeš Matlab i napišeš generator $F(n)$ u njemu.

Matlab će odraditi preciznu aritmetiku za tebe.

U suprotnom slučaju ti treba procedura u VB koja ume da sabira veeeelike brojeve, koju možeš i sam da napišeš. Ideja je da sabiraš Fibonačijeve brojeve dok ne pronađeš onaj čija su 32 donja bita jednaka nuli.

Da li si probao da proceniš koliko je $n$ tog broja. Da li postoji negde dokaz na primer da $n$ ne može biti manje od dvestapedeset milijardi ili tako nešto? Pitanje je da li brute force pristup može bilo šta da uradi.

poz.

Odgovor od frenda :
On Maple it took half day to get to f(1000000000)
On 16-bit asm it took 1min 42sec to find an answer
On 32-bit asm it toom 28sec to get the answer
On Delphi also 28 sec - checked with disassembler - the code matched with my assembly code.

Ja osobno mislim, da je n << 1000000000
Probavam sa matematikom upravo sada :)
Pa ču vam "ako usoijem" dati odgovor, a probajte da to riješite i sami

Pozdrav

Boris

Da li znaš koliko cifara ima $ F(n) $ ako je $ n = 1000000000? Ja ne znam, al evo ti brza procena. Naime $ F(n) $ eksponencijalno raste sa $n$ što se vidi iz funkcije generatrise.

S druge strane broj cifara raste logaritamski sa porastom vrednosti broja tako da bih rekao da je broj cifara broja kog tražiš proporcionalan sa $n$.

A milijardu cifara traži oko milijardu bajtova za pamćenje. Dobro, nije _baš_ tako, al hoću da ti kažem da ti je problem kao malko veći nego što očekuješ, tim pre što ne znaš ni da li broj koji ispunjava tvoj uslov uopšte postoji.

brute force sa matematikom je prespor, treba nešto drugo, kakvu binarnu sličnost gore navedenih postupka ili koja fora fibb sequence/členova u njime, deduktivni pristup u binarnom smislu ????

Nemam pojma, a nemem ni riješenja
Fibonacci[10000000] u attachmentu

ne ide ni u zip !
txt fajl rješenja je dug 2.170.283 bytes !!!!

broj decimalnih mjesta u njemu : 2089877
a početak :

1,12983437822539976031706363774586637294483719048904088151357764324553473116793*E2089877

Proveri da li je broj koji si dobio stvarno resenje ili je samo posledica gubitka preciznosti. To ti kažem zbog onog E u rezultatu.

poz.

Ne to nije rezultat koji bi mogao biti rješenje.

I'm still working on it ...

Svaka pomoč pri izradi programa je dobrodošla

Boris

Heh, evo i dodatnog razloga

>dir /b
fibonacci.asm
fibonacci.exe
fibonacci.obj
Makefile

\>fibonacci.exe
X = *********, time elapsed: 4.828s

can anyone beat this?
(assuming i have PIII 1GHz and average time after 10 runs was 4.8265)

koliko ja vidim,ovo vise nije matematika,pa ti savetujem da isto pitanje postavis u forumu art of programing(ako sam dobro napisala)
istovremeno bih zamolila bilo koga,ko ima volje,da mi objasni oznake tipa $n$ i sl,primetila sam da se to i jos neke dr. oznake koriste ovde,a ja ne znam da ih tumacim.verovatno je neki mat. program,ali ...
poz

Pazite ovako.. Ja kad probam da iskalkulisem Fibenacijev niz sledecom formulom

Ovo je znaci algoritam koji koristim, i misteriozno nakon 24 broja se niz poremeti, evo kako:

Pocetak Fibonacijevog niza
1: 0
2: 1
3: 1
4: 2
5: 3
6: 5
7: 8
8: 13
9: 21
10: 34
11: 55
12: 89
13: 144
14: 233
15: 377
16: 610
17: 987
18: 1597
19: 2584
20: 4181
21: 6765
22: 10946
23: 17711
24: 28657
25: -19168
26: 9489

Dali neko zna zasto se ovo desava? I zasto bas na tom broju?

Naravno. To je u stvari i jedina teskoca kod ovog problemcica.

Stvar je u tome sto su promenjive koje koristis iz nekog razloga po defaultu 16-bitni oznaceni celi brojevi cija vrednost moze da se krece otprilike u granicama -32000 - +32000. Zato ako sabiras dva broja koji ciji je zbir veci od najveceg broja, rezultat se "premota" u minus. Kao ono ako se secas u tetrisu nekada sto je bilo.

Resenje je da umesto 16-bitnih intova koristis 32-bitne, u kom slucaju je granica podignuta na nekoliko milijardi ali opet postoji. To ti na zalost verovatno nece pomoci da resis zadatak.

poz.

Zdravo. Matematicke formule uokvirene dolarskim znakovima poticu iz programa koji se zove TeX (cita se: teh, a pise bas ovako, sa izmestenim slovima!), ciji je autor covek za koga s obzirom da si matematicar sigurno znas: Donald Ervin Knut.

TeX je program za pripremu za stampu lepih knjiga, narocito onih koje imaju u sebi puno matematike.

Ako otvoris neki od svojih udzbenika, recimo neki koji u sebi ima raskosne matematicke formule, vrlo verovatno ces gledati u knjigu koja je napravljena uz upotrebu TeX-a.

Ideja da se formule uokviruju dolarskim znacima na forumu potice od toga sto bi lako moglo da se namesti da server svaku formulicu provuce kroz TeX i od nje napravi slozenu matematicku formulu sa svim notacijskim pogodnostima. Tako ako bih hteo da napisem sumu svih brojeva od 1 do n mogao bih da stavim

$$ \sum_{i=1}^n i $$

sto bi se pojavilo na slici kao grcko veliko sigma, koje ispod ima tekst i=1 a iznad n i samo i kao argument. Izmedju ostalog u linku koji je dat na dnu poruke imas objasnjenu sintaksu TeX jezika

Ne treba da napominjem da svaki pravi matematicar mora da zna TeX. Zato se sto pre baci na ucenje. :) Za svakodnevnu upotrebu je pogodnija nadogradnja TeX-a koja se zove LaTeX (cita se: lateh, i pise bas ovako, sa izmestenim slovima).

www.ctan.org/tex-archive/info/lshort/english/lshort.pdf

poz.

Ok je to za niz... To moze da se resi pravljenjem sopstvene rutine za unos i sabiranje brojeva kroz array ili matricu..

y= F(x)/2&sup3;&sup2; &#8594; 0

Fora je u tome sto 2&sup3;&sup2; neki konacan broj. Ako pustimo da F(x) tezi beskonacnosti dobicemo rezultat:

y >= 1


JEDINI nacin da dobijemo 0 je da napravimo neku gresku u deljenju i da pobrkamo znakove...

Jesdnostavno, bilo sta podeljeno sa nesto konacno ce biti >0, ovo ne znam kako resiti, ali mi se sve cini da je to kao onaj 'dokaz', 1+1=3 gde se gresi sa znakovima i matematickim pravilima da bi se dobio rezultat...

E sad... Ako pustimo da F(x) &#8594; &#8734; radi analiziranja ovog problema vec moramo da ulazimo u domen vise matematike... A uostalom beskonacnost jos uvek nije definisanja niti je ponasanje brojeva u beskonacnosti jos uvek dovoljno ispitano da bi mi mogli da navedemo resenje ovog problema.

Poznano
X = *********

X je je moguče skalkulirati sa kojim dobrim asm ili c++.

But i need help with that ?

Zanima me riješenje ili programčič ili još koje moguče prepostavke, kojih pri F brojevima ima mnogo a ima i mnogo sličnosti u binarnom pristupu problema.

Boris, still having a lots of problems regarding this problem

Borise, mislim da imam rešenje.

Stvar je više nego trivijalna. Osećam se kao potpuni glupander.

Uopšte se ne traži da ti izračunaš o kom se broju radi. Treba ti samo odgovarajuće $n$ za $F(n)$. Pošto te interesuje samo broj po modulu, sve što treba je da računaš $F(n)$ po modulu 2^32, a ne ceo broj!!! To se automatski radi na PC'ju ako je unsigned long veliki 32 bita kao sto jeste.

Znači, program koji daje rešenje:



A resenje je:

3221225472

i dobija se skoro trenutno na mojoj masini.

Ako te zanima i izračunavanje konkretnog broja, mogu da napišem jedan brzi algoritam, ali ćeš morati sam da pišeš program pošto moram da hvatam avion kući. :)

Iskoristio bih priliku da se zahvalim venturi na ideji, odnosno na tome što me je naveo da ponovo pročitam postavku zadatka. On je u stvari prvi našao rešenje, samo je zaboravio da namesti da promenljive budu unsigned long umesto signed int.

f.

!?!?

Malo matematičke korektnosti u forumu o matematici ne bi bilo na odmet... :)

f.

kad sam ja došao do pravog riješenja ti si več upisao pravo, da ja 3221225472
prvo riješenje.

Hvala svima, jako zanimljivo.
A ja sam došao na trag rješenju uz pomoč zdrave matematičke logike i MOD funkcije pri F brojevima

Još jedanput : Hvala

Boris

pozdrav ucesnicima u raspravi(za koju mislim da je najuspelija do sada na ovom forumu)
(ma,nije fer da budete prisutniji ovde,jer kad ja dodjem,skoro da nemam sta vise da dodam!...salim se,naravno...ne mozemo svi imati jednako slobodnog vremena)

posebno pozdravljam filimila,zbog njegove korektnosti i konstruktivne direkcije problema,s tim sto sad moram da kazem da mat. programe ne mora da zna pravi matematicar,vec savremen matematicar(koji za to ima mogucnosti i volje).
hvala na objasnjenju,poslusacu tvoj savet
takodje mislim da je ovakva tema mnogo bolja,interesantnija i produktivnija od resavanja klasicnih zadataka i nadam se da ce ih vise biti
poz

Daj ljudi ovo se u programu Mathematica reši za sekund:
Ovo daje formulu za n-ti Fabonačijev broj

Kada dobiješ rezultat možeš koristiti Solve ili FindRoot za rešavanje:
!(Mod[(2^((-1) - n) (((-((1 - @5))^(1 + n)) + ((1 + @5))
^(1 + n))))/@5 , 2^32] == 0)

poz.

Kajla: Gde ima da se skine Mathematica

Fibonacijevi brojevi u Python-u (preuzeto iz Python tutoriala):


(tacke zameniti sa razmacima, jer ovaj code tag sve to pojede)
Poziva se sa:


Poz, alex.

Hvala, za nagradu opet jedna dobar puzzle

Nemam pojma...ja sam kupio CD sa Mathematica 4.0.0.0 za 5 DEM.

poz.

Da zaključimo na kraju da je n=118 rešenje zadatka, tj 2^32|f(118).

poz.

f(118)=2046711111473984623691759
f(118) mod 2^32=4

Kako to može da bude riješenje ???


n=3221225472 !!!

Negde sam pogrešio...

poz.