We know Fibonacci number, Fn = Fn-1 + Fn-2.
First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …. .
Here are some interesting facts about Fibonacci number :
1. Pattern in Last digits of Fibonacci numbers :
Last digits of first few Fibonacci Numbers are :
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, ...
The series of last digits repeats with a cycle length of 60 (Refer this for explanations of this result).
C++
#include <bits/stdc++.h>
using namespace std;
#define max 100
int main()
{
long long int arr[max];
arr[0] = 0;
arr[1] = 1;
int i = 0;
for (i = 2; i < max; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
for (i = 1; i < max - 1; i++) {
cout << i << endl;
if ((arr[i] % 10 == 0) && (arr[i + 1] % 10 == 1)) {
break ;
}
}
cout << "Sequence is repeating after index " << i
<< endl;
}
|
C
#include <stdio.h>
#define max 100
int main()
{
long long int arr[max];
arr[0] = 0;
arr[1] = 1;
int i = 0;
for (i = 2; i < max; i++)
arr[i] = arr[i - 1] + arr[i - 2];
for (i = 1; i < max - 1; i++)
{
if ((arr[i] % 10 == 0) && (arr[i + 1] % 10 == 1))
break ;
}
printf ( "Sequence is repeating after index %d" , i);
}
|
Java
class GFG{
static int max= 100 ;
public static void main(String[] args)
{
long [] arr= new long [max];
arr[ 0 ] = 0 ;
arr[ 1 ] = 1 ;
int i= 0 ;
for (i = 2 ; i < max; i++)
arr[i] = arr[i- 1 ] + arr[i- 2 ];
for (i = 1 ; i < max - 1 ; i++)
{
if ((arr[i] % 10 == 0 ) && (arr[i+ 1 ] % 10 == 1 ))
break ;
}
System.out.println( "Sequence is repeating after index " +i);
}
}
|
Python3
if __name__ = = '__main__' :
max = 100
arr = [ 0 for i in range ( max )]
arr[ 0 ] = 0
arr[ 1 ] = 1
for i in range ( 2 , max ):
arr[i] = arr[i - 1 ] + arr[i - 2 ]
for i in range ( 1 , max - 1 ):
if ((arr[i] % 10 = = 0 ) and (arr[i + 1 ] % 10 = = 1 )):
break
print ( "Sequence is repeating after index" , i)
|
C#
class GFG{
static int max=100;
public static void Main()
{
long [] arr= new long [max];
arr[0] = 0;
arr[1] = 1;
int i=0;
for (i = 2; i < max; i++)
arr[i] = arr[i-1] + arr[i-2];
for (i = 1; i < max - 1; i++)
{
if ((arr[i] % 10 == 0) && (arr[i+1] % 10 == 1))
break ;
}
System.Console.WriteLine( "Sequence is repeating after index " +i);
}
}
|
Javascript
<script>
var max = 100;
var arr = Array(max).fill(0);
arr[0] = 0;
arr[1] = 1;
var i = 0;
for (i = 2; i < max; i++)
arr[i] = arr[i - 1] + arr[i - 2];
for (i = 1; i < max - 1; i++)
{
if ((arr[i] % 10 == 0) && (arr[i + 1] % 10 == 1))
break ;
}
document.write( "Sequence is repeating after index " + i);
</script>
|
PHP
<?php
$arr [0] = 0;
$arr [1] = 1;
for ( $i = 2; $i < 100; $i ++)
$arr [ $i ] = $arr [ $i -1] +
$arr [ $i -2];
for ( $i = 1; $i <100 - 1; $i ++)
{
if (( $arr [ $i ] % 10 == 0) &&
( $arr [ $i +1] % 10 == 1))
break ;
}
echo "Sequence is repeating after" ,
" index " , $i ;
?>
|
Sequence is repeating after index 60
Time complexity of the given program is O(max), as it runs two loops from 2 to max-1 and performs constant-time operations inside both loops. Hence, the time complexity is linear in terms of the value of max.
Space complexity of the program is O(max), as it creates an array of size max to store the Fibonacci numbers. The space required for other variables used in the program is constant and negligible compared to the array size. Therefore, the space complexity is also linear in terms of the value of max.
2. Factors of Fibonacci number : On careful observation, we can observe the following thing :
- Every 3-rd Fibonacci number is a multiple of 2
- Every 4-th Fibonacci number is a multiple of 3
- Every 5-th Fibonacci number is a multiple of 5
- Every 6-th Fibonacci number is a multiple of 8
C++
#include<iostream>
using namespace std;
#define MAX 90
int main()
{
long long int arr[MAX], index1[MAX], index2[MAX];
long long int index3[MAX], index4[MAX];
arr[0] = 0;
arr[1] = 1;
for ( int i = 2; i < MAX; i++)
arr[i] = arr[i-1] + arr[i-2];
int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
for ( int i = 0; i < MAX; i++)
{
if (arr[i] % 2 == 0)
index1[c1++] = i;
if (arr[i] % 3 == 0)
index2[c2++] = i;
if (arr[i] % 5 == 0)
index3[c3++] = i;
if (arr[i] % 8 == 0)
index4[c4++] = i;
}
cout<< "Index of Fibonacci numbers divisible by"
" 2 are :\n" ;
for ( int i = 0; i < c1; i++)
cout<< " " << index1[i];
cout<< "\n" ;
cout<< "Index of Fibonacci number divisible by"
" 3 are :\n" ;
for ( int i = 0; i < c2; i++)
cout<< " " << index2[i];
cout<< "\n" ;
cout<< "Index of Fibonacci number divisible by"
" 5 are :\n" ;
for ( int i = 0; i < c3; i++)
cout<< " " << index3[i];
cout<< "\n" ;
cout<< "Index of Fibonacci number divisible by"
" 8 are :\n" ;
for ( int i = 0; i < c4; i++)
cout<< " " <<index4[i];
cout<< "\n" ;
}
|
C
#include<stdio.h>
#define MAX 90
int main()
{
long long int arr[MAX], index1[MAX], index2[MAX];
long long int index3[MAX], index4[MAX];
arr[0] = 0;
arr[1] = 1;
for ( int i = 2; i < MAX; i++)
arr[i] = arr[i-1] + arr[i-2];
int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
for ( int i = 0; i < MAX; i++)
{
if (arr[i] % 2 == 0)
index1[c1++] = i;
if (arr[i] % 3 == 0)
index2[c2++] = i;
if (arr[i] % 5 == 0)
index3[c3++] = i;
if (arr[i] % 8 == 0)
index4[c4++] = i;
}
printf ( "Index of Fibonacci numbers divisible by"
" 2 are :\n" );
for ( int i = 0; i < c1; i++)
printf ( "%d " , index1[i]);
printf ( "\n" );
printf ( "Index of Fibonacci number divisible by"
" 3 are :\n" );
for ( int i = 0; i < c2; i++)
printf ( "%d " , index2[i]);
printf ( "\n" );
printf ( "Index of Fibonacci number divisible by"
" 5 are :\n" );
for ( int i = 0; i < c3; i++)
printf ( "%d " , index3[i]);
printf ( "\n" );
printf ( "Index of Fibonacci number divisible by"
" 8 are :\n" );
for ( int i = 0; i < c4; i++)
printf ( "%d " , index4[i]);
printf ( "\n" );
}
|
Java
class GFG
{
static int MAX= 90 ;
public static void main(String[] args)
{
long [] arr= new long [MAX];
long [] index1= new long [MAX];
long [] index2= new long [MAX];
long [] index3= new long [MAX];
long [] index4= new long [MAX];
arr[ 0 ] = 0 ;
arr[ 1 ] = 1 ;
for ( int i = 2 ; i < MAX; i++)
arr[i] = arr[i - 1 ] + arr[i - 2 ];
int c1 = 0 , c2 = 0 , c3 = 0 , c4 = 0 ;
for ( int i = 0 ; i < MAX; i++)
{
if (arr[i] % 2 == 0 )
index1[c1++] = i;
if (arr[i] % 3 == 0 )
index2[c2++] = i;
if (arr[i] % 5 == 0 )
index3[c3++] = i;
if (arr[i] % 8 == 0 )
index4[c4++] = i;
}
System.out.print( "Index of Fibonacci numbers divisible by" +
" 2 are :\n" );
for ( int i = 0 ; i < c1; i++)
System.out.print(index1[i] + " " );
System.out.print( "\n" );
System.out.print( "Index of Fibonacci number divisible by" +
" 3 are :\n" );
for ( int i = 0 ; i < c2; i++)
System.out.print(index2[i] + " " );
System.out.print( "\n" );
System.out.print( "Index of Fibonacci number divisible by" +
" 5 are :\n" );
for ( int i = 0 ; i < c3; i++)
System.out.print(index3[i] + " " );
System.out.print( "\n" );
System.out.print( "Index of Fibonacci number divisible by" +
" 8 are :\n" );
for ( int i = 0 ; i < c4; i++)
System.out.print(index4[i] + " " );
System.out.print( "\n" );
}
}
|
Python3
MAX = 90 ;
arr = [ 0 ] * ( MAX );
index1 = [ 0 ] * ( MAX );
index2 = [ 0 ] * ( MAX );
index3 = [ 0 ] * ( MAX );
index4 = [ 0 ] * ( MAX );
arr[ 0 ] = 0 ;
arr[ 1 ] = 1 ;
for i in range ( 2 , MAX ):
arr[i] = arr[i - 1 ] + arr[i - 2 ];
c1, c2, c3, c4 = 0 , 0 , 0 , 0 ;
for i in range ( MAX ):
if (arr[i] % 2 = = 0 ):
index1[c1] = i;
c1 + = 1 ;
if (arr[i] % 3 = = 0 ):
index2[c2] = i;
c2 + = 1 ;
if (arr[i] % 5 = = 0 ):
index3[c3] = i;
c3 + = 1 ;
if (arr[i] % 8 = = 0 ):
index4[c4] = i;
c4 + = 1 ;
print ( "Index of Fibonacci numbers" ,
"divisible by 2 are :" );
for i in range (c1):
print (index1[i], end = " " );
print ("");
print ( "Index of Fibonacci number" ,
"divisible by 3 are :" );
for i in range (c2):
print (index2[i], end = " " );
print ("");
print ( "Index of Fibonacci number" ,
"divisible by 5 are :" );
for i in range (c3):
print (index3[i], end = " " );
print ("");
print ( "Index of Fibonacci number" ,
"divisible by 8 are :" );
for i in range (c4):
print (index4[i], end = " " );
print ("");
|
C#
class GFG{
static int MAX = 90;
static void Main()
{
long [] arr = new long [MAX];
long [] index1 = new long [MAX];
long [] index2 = new long [MAX];
long [] index3 = new long [MAX];
long [] index4 = new long [MAX];
arr[0] = 0;
arr[1] = 1;
for ( int i = 2; i < MAX; i++)
arr[i] = arr[i-1] + arr[i-2];
int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
for ( int i = 0; i < MAX; i++)
{
if (arr[i] % 2 == 0)
index1[c1++] = i;
if (arr[i] % 3 == 0)
index2[c2++] = i;
if (arr[i] % 5 == 0)
index3[c3++] = i;
if (arr[i] % 8 == 0)
index4[c4++] = i;
}
System.Console.Write( "Index of Fibonacci numbers" +
"divisible by 2 are :\n" );
for ( int i = 0; i < c1; i++)
System.Console.Write(index1[i]+ " " );
System.Console.Write( "\n" );
System.Console.Write( "Index of Fibonacci number " +
" divisible by 3 are :\n" );
for ( int i = 0; i < c2; i++)
System.Console.Write(index2[i]+ " " );
System.Console.Write( "\n" );
System.Console.Write( "Index of Fibonacci number " +
"divisible by 5 are :\n" );
for ( int i = 0; i < c3; i++)
System.Console.Write(index3[i]+ " " );
System.Console.Write( "\n" );
System.Console.Write( "Index of Fibonacci number " +
"divisible by 8 are :\n" );
for ( int i = 0; i < c4; i++)
System.Console.Write(index4[i]+ " " );
System.Console.Write( "\n" );
}
}
|
Javascript
var MAX=90;
var arr= new Array(MAX);
var index1= new Array(MAX);
var index2= new Array(MAX);
var index3= new Array(MAX);
var index4= new Array(MAX);
arr[0] = 0;
arr[1] = 1;
for ( var i = 2; i < MAX; i++)
arr[i] = arr[i - 1] + arr[i - 2];
var c1 = 0, c2 = 0, c3 = 0, c4 = 0;
for ( var i = 0; i < MAX; i++)
{
if (arr[i] % 2 == 0)
index1[c1++] = i;
if (arr[i] % 3 == 0)
index2[c2++] = i;
if (arr[i] % 5 == 0)
index3[c3++] = i;
if (arr[i] % 8 == 0)
index4[c4++] = i;
}
document.write( "Index of Fibonacci numbers divisible by" +
" 2 are :\n" );
for ( var i = 0; i < c1; i++)
document.write(index1[i] + " " );
document.write( "\n" );
document.write( "Index of Fibonacci number divisible by" +
" 3 are :\n" );
for ( var i = 0; i < c2; i++)
document.write(index2[i] + " " );
document.write( "\n" );
document.write( "Index of Fibonacci number divisible by" +
" 5 are :\n" );
for ( var i = 0; i < c3; i++)
document.write(index3[i] + " " );
document.write( "\n" );
document.write( "Index of Fibonacci number divisible by" +
" 8 are :\n" );
for ( var i = 0; i < c4; i++)
document.write(index4[i] + " " );
document.write( "\n" );
|
PHP
<?php
$MAX = 90;
$arr = array ( $MAX );
$index1 = array ( $MAX );
$index2 = array ( $MAX );
$index3 = array ( $MAX );
$index4 = array ( $MAX );
$arr [0] = 0;
$arr [1] = 1;
for ( $i = 2; $i < $MAX ; $i ++)
{
$arr [ $i ] = $arr [ $i - 1] + $arr [ $i - 2];
}
$c1 = 0;
$c2 = 0;
$c3 = 0;
$c4 = 0;
for ( $i = 0; $i < $MAX ; $i ++)
{
if ( $arr [ $i ] % 2 == 0)
$index1 [ $c1 ++] = $i ;
if ( $arr [ $i ] % 3 == 0)
$index2 [ $c2 ++] = $i ;
if ( $arr [ $i ] % 5 == 0)
$index3 [ $c3 ++] = $i ;
if ( $arr [ $i ] % 8 == 0)
$index4 [ $c4 ++] = $i ;
}
echo "Index of Fibonacci numbers divisible by" .
" 2 are :\n" ;
for ( $i = 0; $i < $c1 ; $i ++)
echo $index1 [ $i ] . " " ;
echo "\n" ;
echo "Index of Fibonacci number divisible by" .
" 3 are :\n" ;
for ( $i = 0; $i < $c2 ; $i ++)
echo $index2 [ $i ] . " " ;
echo "\n" ;
echo "Index of Fibonacci number divisible by" .
" 5 are :\n" ;
for ( $i = 0; $i < $c3 ; $i ++)
echo $index3 [ $i ] . " " ;
echo "\n" ;
echo "Index of Fibonacci number divisible by" .
" 8 are :\n" ;
for ( $i = 0; $i < $c4 ; $i ++)
echo $index4 [ $i ] . " " ;
echo "\n" ;
?>
|
Index of Fibonacci numbers divisible by 2 are :
0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45
48 51 54 57 60 63 66 69 72 75 78 81 84 87
Index of Fibonacci number divisible by 3 are :
0 4 8 12 16 20 24 28 32 36 40 44 48 52
56 60 64 68 72 76 80 84 88
Index of Fibonacci number divisible by 5 are :
0 5 10 15 20 25 30 35 40 45 50
55 60 65 70 75 80 85
Index of Fibonacci number divisible by 8 are :
0 6 12 18 24 30 36 42 48
54 60 66 72 78 84
Time Complexity:
The program uses a single for loop of size MAX, to calculate and store the Fibonacci numbers in the array. Hence, the time complexity for this part of the program is O(MAX). The program then uses another for loop of size MAX, to check each number in the array for divisibility by 2, 3, 5, and 8. The time complexity for this part of the program is also O(MAX). Therefore, the overall time complexity of the program is O(MAX).
Space Complexity:
The program uses an array of size MAX to store the Fibonacci numbers. It also uses four separate arrays of sizes c1, c2, c3, and c4, to store the indexes of the Fibonacci numbers that are divisible by 2, 3, 5, and 8 respectively. The maximum size of these arrays is equal to MAX/3 (when all Fibonacci numbers are divisible by 2). Therefore, the space complexity of the program is O(MAX).
3. Fibonacci number with index number factor : We have some Fibonacci number like F(1) = 1 which is divisible by 1, F(5) = 5 which is divisible by 5, F(12) = 144 which is divisible by 12, F(24) = 46368 which is divisible by 24, F(25) = 75025 which is divisible by 25. This type of index number follow a certain pattern. First, let’s keep a look on those index number :
1, 5, 12, 24, 25, 36, 48, 60, 72, 84, 96, 108, 120, 125, 132, …..
On observing it, this series is made up of every number that is multiple of 12 as well as all the number that satisfies the condition of pow(5, k), where k = 0, 1, 2, 3, 4, 5, 6, 7, …….
C++
#include<iostream>
using namespace std;
#define MAX 100
int main()
{
long long int arr[MAX];
arr[0] = 0;
arr[1] = 1;
for ( int i = 2; i < MAX; i++)
arr[i] = arr[i-1] + arr[i-2];
cout<< "Fibonacci numbers divisible by "
"their indexes are :\n" ;
for ( int i = 1; i < MAX; i++)
if (arr[i] % i == 0)
cout<< " " << i;
}
|
C
#include<stdio.h>
#define MAX 100
int main()
{
long long int arr[MAX];
arr[0] = 0;
arr[1] = 1;
for ( int i = 2; i < MAX; i++)
arr[i] = arr[i-1] + arr[i-2];
printf ( "Fibonacci numbers divisible by "
"their indexes are :\n" );
for ( int i = 1; i < MAX; i++)
if (arr[i] % i == 0)
printf ( "%d " , i);
}
|
Java
class GFG
{
static int MAX = 100 ;
public static void main(String[] args)
{
long [] arr = new long [MAX];
arr[ 0 ] = 0 ;
arr[ 1 ] = 1 ;
for ( int i = 2 ; i < MAX; i++)
arr[i] = arr[i - 1 ] + arr[i - 2 ];
System.out.print( "Fibonacci numbers divisible by " +
"their indexes are :\n" );
for ( int i = 1 ; i < MAX; i++)
if (arr[i] % i == 0 )
System.out.print(i + " " );
}
}
|
Python3
if __name__ = = '__main__' :
MAX = 100
arr = [ 0 for i in range ( MAX )]
arr[ 0 ] = 0
arr[ 1 ] = 1
for i in range ( 2 , MAX ):
arr[i] = arr[i - 1 ] + arr[i - 2 ]
print ( "Fibonacci numbers divisible by their indexes are :" )
for i in range ( 1 , MAX ):
if (arr[i] % i = = 0 ):
print (i,end = " " )
|
C#
using System;
class GFG
{
static int MAX = 100;
static void Main()
{
long [] arr = new long [MAX];
arr[0] = 0;
arr[1] = 1;
for ( int i = 2; i < MAX; i++)
arr[i] = arr[i - 1] + arr[i - 2];
Console.Write( "Fibonacci numbers divisible by " +
"their indexes are :\n" );
for ( int i = 1; i < MAX; i++)
if (arr[i] % i == 0)
System.Console.Write(i+ " " );
}
}
|
Javascript
var MAX = 100;
var arr = new Array(MAX);
arr[0] = 0;
arr[1] = 1;
for ( var i = 2; i < MAX; i++)
arr[i] = arr[i - 1] + arr[i - 2];
document.write( "Fibonacci numbers divisible by their indexes are :" );
for ( var i = 1; i < MAX; i++)
if (arr[i] % i == 0)
document.write(i + " " );
|
Fibonacci numbers divisible by their indexes are :
1 5 12 24 25 36 48 60 72 96
4. Value of f(n-1)*f(n+1) – f(n)*f(n) is (-1)n. Please refer Cassini’s Identity for details.
5. The sum of any ten consecutive Fibonacci numbers is divisible by 11.
Example: 0+1+1+ 2+3+ 5+ 8+13+21+34 =88 which is divisible by 11.
Proof: Just write every term in the sum in terms of F1 and F2, keeping in mind that Fn = Fn-1 + Fn-2.
F1+F2+(F1+F2)+(F1+2F2)+(2F1+3F2)+(3F1+5F2)+(5F1+8F2)+(8F1+13F2)+(13F1+21F2)+(21F1+34F2).
Then the sum is clearly equal to 55F1+88F2=11(5F1+8F2), which is divisible by 11.
Reference :
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html
Contact Us