Hi community
This post going to explains about how to find no of digits in nth Fibonacci. Most of you must be familiar with Fibonacci numbers.
Check this Wikipedia article if not.
link text
Given a no N , we have to find the no of digits in nth Fibonacci.
Input : n = 12
Output : 3
12'th Fibonacci number is 144 and it has
3 digits
Approach 1-
calculate the the nth term of Fibonacci series.
//Fibonacci Series using Recursion
#include <iostream>
using namespace std;
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 12,s,count=0;
s=fib(n);
while(s!=0)
{
s /= 10; // n = n/10
++count;
}
printf("Number of digits: %d",count);
return 0;
}
Approach 2-
Though the first approach works , we have a more efficient direct way to do this using Binet’s Formula.
No of digits in f(N) =Log10Fib(n)
= Log10(Φn / √ 5)
= n*Log10(Φ) - Log10√5
= n*Log10(Φ) - (Log105)/2
Implememntation in c++
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int i,n;
scanf("%lli",n);
// Formula used (n * log(phi) - (log 5) / 2)
i=ceil((n * log10(1.6180339887498948)) -
((log10(5)) / 2));
printf("Number of Digits : %d",i);
return 0;
}
Happy Coding …
Edit- Though Binet’s Formula is an approximate formula for calculating nth term , its is viable to use it to calculate no of digits in nth term.