Fibonacci Numbers

A program to generate Fibonacci numbers. This again is an elementary level program.

 

 

/***************************************************************
 Program to print the first n fibonacci series
 n is taken as input
 0 1 1 2 3 5 8 ...
***************************************************************/

#include <stdio.h>

int main(int argc, char* argv[])
{
 int n; // input
 int fib1, fib2, fib3;  
 int i;
 
 // get input from user
 printf("Program to print first n Fibonacci Series\n");
 printf("Enter n:");
 scanf("%d", &n);
 
 if (n <= 0)
 {
  printf("Invalid value of n. Please enter value > 0\n");
  goto exit;
 }
 
 // print fibo series
 fib1=0; fib2=0; fib3=1;
 
 printf("The %d fibonacci numbers are \n", n);
 for (i=0; i<n; i++)
 {
  printf("%d ", fib1);
  fib2=fib3; fib3=fib1;
  fib1 = fib2 + fib3;
 }
 printf("\n");
 
exit:
 printf("Exit from Program\n");
 
 return 0;
}

/***************************************************************
Output:

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:-1
Invalid value of n. Please enter value > 0
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:0
Invalid value of n. Please enter value > 0
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:1
The 1 fibonacci numbers are
0
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:2
The 2 fibonacci numbers are
0 1
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:3
The 3 fibonacci numbers are
0 1 1
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:5
The 5 fibonacci numbers are
0 1 1 2 3
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:10
The 10 fibonacci numbers are
0 1 1 2 3 5 8 13 21 34
Exit from Program

E:\VSProjs\blog>2_Fibonacci.exe
Program to print first n Fibonacci Series
Enter n:20
The 20 fibonacci numbers are
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Exit from Program

E:\VSProjs\blog>

***************************************************************/

 

Notes : <source http://en.wikipedia.org/wiki/Fibonacci_number - its a complete copy paste job>

 

 

         In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence : 0 1 1 2 3 5 8 13 … Obtained by the relation F(n) = F(n-1) + F(n-2), the seed values used are F(0)=0, F(1)=1

 

                Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a newly born pair of rabbits, one male, one female, are put in a field; rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits; rabbits never die and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was: how many pairs will there be in one year?

• At the end of the first month, they mate, but there is still only 1 pair.
• At the end of the second month the female produces a new pair, so now there are 2 pairs of rabbits in the field.
• At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field.
• At the end of the fourth month, the original female has produced yet another new pair, the female born two months ago produces her first pair also, making 5 pairs.

         At the end of the nth month, the number of pairs of rabbits is equal to the number of new pairs (which is the number of pairs in month n − 2) plus the number of pairs alive last month (n − 1). This is the nth Fibonacci number.

 

        On similar lines we have "negafibonacci" numbers, satisfying the relation

 

Thus the fibonacci series :

F−8

F−7

F−6

F−5

F−4

F−3

F−2

F−1

F0

F1

F2

F3

F4

F5

F6

F7

F8

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

Relation with Golden Ratio

The Fibonacci numbers have a closed-form solution. It has become known as Binet's formula.

where

is the golden ratio and

for the purpose of computation we use the following form :

  

  

Recognizing Fibonacci Numbers

      On similar lines we can use the following formula to check if a given number is a fibonacci number :

 

or alternatively
         a positive integer z is a Fibonacci number if and only if one of or is a perfect square.

  

  

Applications

1. The Fibonacci numbers are important in the computational run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers: the worst case input for this algorithm is a pair of consecutive Fibonacci numbers.
    
    
2. The Fibonacci numbers are also an example of a complete sequence. This means that every positive integer can be written as a sum of Fibonacci numbers, where any one number is used once at most. Specifically, every positive integer can be written in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is known as Zeckendorf's theorem, and a sum of Fibonacci numbers that satisfies these conditions is called a Zeckendorf representation. The Zeckendorf representation of a number can be used to derive its Fibonacci coding.
    
    
3. Fibonacci numbers are used by some pseudorandom number generators.
4. Fibonacci numbers are used in a polyphase version of the merge sort algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers
    
    
5. The Fibonacci cube is an undirected graph with a Fibonacci number of nodes that has been proposed as a network topology for parallel computing.
    
    
6. Fibonacci numbers arise in the analysis of the Fibonacci heap data structure.
    
    
7. The Fibonacci number series is used for optional lossy compression in the IFF 8SVX audio file format used on Amiga computers. The number series compands the original audio wave similar to logarithmic methods such as µ-law

Apart from this there are a bunch of properties about fibonacci numbers. I found This to be the most interesting one:

 

The Fibonacci numbers can be found in different ways in the sequence of binary strings.

 

• The number of binary strings of length n without consecutive 1s is the Fibonacci number F_n+2. For example, out of the 16 binary strings of length 4, there are F₆ = 8 without consecutive 1s – they are 0000, 0100, 0010, 0001, 0101, 1000, 1010 and 1001. By symmetry, the number of strings of length n without consecutive 0s is also F_n+2.
• The number of binary strings of length n without an odd number of consecutive 1s is the Fibonacci number F_n+1. For example, out of the 16 binary strings of length 4, there are F₅ = 5 without an odd number of consecutive 1s – they are 0000, 0011, 0110, 1100, 1111.
• The number of binary strings of length n without an even number of consecutive 0s or 1s is 2F_n. For example, out of the 16 binary strings of length 4, there are 2F₄ = 6 without an even number of consecutive 0s or 1s – they are 0001, 1000, 1110, 0111, 0101, 1010.

There are more topics on observing fibonacci patterns in Nature, combinatorial identities etc. The brave can march ahead to explore.