Hopp til innhald

Fibonaccifølgja

Frå Wikipedia – det frie oppslagsverket
Rektangel der sidene i kvar er tal frå fibonaccifølgja.

Fibonaccifølgja er ei følgje av tal der kvart tal unntatt dei to første er summen av dei to føregåande.[1][2] I sin vidaste definisjon kan dei to første tala vere kva som helst, men mest vanleg er å starte på anten 1 og 1 eller 0 og 1:

eller

.
Bokside frå Liber Abaci av Fibonacci. I boksen til høgre er fibonaccifølgja lagt fram i rekkjefølgje med romerske og arabiske tal.

Fibonaccifølgja har namn etter Leonardo Fibonacci sitt forsøk på å beskrive populasjonsvekst hjå ei tenkt gruppe kaninar. Ho blei likevel omtalt mykje tidlegare. Innan gammal indisk matematikk blei ho brukt til å studera prosodi i sanskrit.[3][4] Innan verselæra på sanskrit ønska ein å finna alle mønster av lange (L) stavingar som er 2 einingar lange, og korte (K) stavingar som er 1 eining lang. Tel ein dei ulike mønstera av L og K med ei viss lengd får ein fibonaccifølgja: Talet på mønster som er m korte statvingar lang er fibonaccitalet Fm + 1.[5]

Å finne fibonaccifølgja

[endre | endre wikiteksten]

Følgjande program i programmeringsspråket C genererer følgja av fibonaccital som ikkje overstig den maksimale verdien av den største heiltalsdatatypen i standardbiblioteket til C99. Dei to første tala er frivillige argument på kommandolinja.

#include <stdio.h>
#include <stdint.h>
int main(int argc, char *argv[]){
	uintmax_t i=1, j=1;
	if(argc == 3){
		i = strtoll(argv[1], NULL, 0);
		j = strtoll(argv[2], NULL, 0);
	}
	printf("%llu", i);
	do{
		printf("\n%llu", j);
		i = i + j;
		if(i < j) break;
		printf("\n%llu", i);
		j = j + i;
	}while(j > i);
	putchar('\n');
	return 0;
}

Med to eitt-tal som start og 64 bit øvre talgrense, kjem desse 93 tala ut. Dette tek omkring 2 - 10 millisekund på ein moderne PC.

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
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738


  1. Beck & Geoghegan 2010.
  2. Bóna 2011, s. 180.
  3. Singh, Parmanand (1985), «The So-called Fibonacci numbers in ancient and medieval India», Historia Mathematica 12 (3): 229–44, doi:10.1016/0315-0860(85)90021-7 
  4. Knuth, Donald (1968), The Art of Computer Programming 1, Addison Wesley, ISBN 81-7758-754-4, «Before Fibonacci wrote his work, the sequence Fn had already been discussed by Indian scholars, who had long been interested in rhythmic patterns... both Gopala (before 1135 AD) and Hemachandra (c. 1150) mentioned the numbers 1,2,3,5,8,13,21 explicitly [see P. Singh Historia Math 12 (1985) 229–44]" p. 100 (3d ed)...» 
  5. Knuth, Donald (2006), The Art of Computer Programming, 4. Generating All Trees – History of Combinatorial Generation, Addison–Wesley, s. 50, ISBN 978-0-321-33570-8, «it was natural to consider the set of all sequences of [L] and [S] that have exactly m beats. ...there are exactly Fm+1 of them. For example the 21 sequences when m = 7 are: [gives list]. In this way Indian prosodists were led to discover the Fibonacci sequence, as we have observed in Section 1.2.8 (from v.1)» 
  • Ball, Keith M (2003), «8: Fibonacci's Rabbits Revisited», Strange Curves, Counting Rabbits, and Other Mathematical Explorations, Princeton, NJ: Princeton University Press, ISBN 0-691-11321-1 .
  • Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics, New York: Springer .
  • Bóna, Miklós (2011), A Walk Through Combinatorics (3rd utg.), New Jersey: World Scientific .
  • Lemmermeyer, Franz (2000), Reciprocity Laws, New York: Springer, ISBN 3-540-66957-4 .
  • Lucas, Édouard (1891), Théorie des nombres (på fransk) 1, Gauthier-Villars 
  • Pisano, Leonardo (2002), Fibonacci's Liber Abaci: A Translation into Modern English of the Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Sigler, Laurence E, trans, Springer, ISBN 0-387-95419-8