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. 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 
.

Historie
mini|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. 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.

Å finne fibonaccifølgja
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

Kjelder

 .
 .
 .
 .



Kategori:Heiltalsfølgjer
Kategori:Matematiske relasjonar
Kategori:Rekursjon