Finding number of digits in n’th Fibonacci number

Given a number n, find number of digits in n’th Fibonacci Numbers. First few Fibinacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….

Examples:

Input : n = 6
Output : 1
6'th Fibonacci number is 8 and it has 
1 digit.

Input : n = 12
Output : 3
12'th Fibonacci number is 144 and it has 
3 digits.

A simple solution is to find n’th Fibonacci Number and then count number of digits in it. This solution may lead to overflow problems for large values of n.

A direct way is to count number of digits in the nth Fibonacci number using below Binet’s Formula.

fib(n) = (Φⁿ - Ψ^-n) / √5
where
Φ = (1 + √5) / 2
Ψ = (1 - √5) / 2

The above formula can be simplified, 
fib(n) = round(Φⁿ / ? 5) 
Here round function indicates nearest integer.

Count of digits in Fib(n) = Log₁₀Fib(n)
                          = Log₁₀(Φⁿ / √5)
                          = n*Log₁₀(Φ) - Log₁₀√5
                          = n*Log₁₀(Φ) - (Log₁₀5)/2

As mentioned in this G-Fact, this formula doesn’t seem to work and produce correct Fibonacci numbers due to limitations of floating point arithmetic. However, it looks viable to use this formula to find count of digits in n’th Fibonacci number.

Below is the implementation of above idea :

div class="responsive-tabs">

C++

/* C++ program to find number of digits in nth 
   Fibonacci number */
#include<bits/stdc++.h> 
using namespace std; 
  
// This function returns the number of digits 
// in nth Fibonacci number after ceiling it 
// Formula used (n * log(phi) - (log 5) / 2) 
long long numberOfDigits(long long n) 
{ 
    if (n == 1) 
        return 1; 
  
    // using phi = 1.6180339887498948 
    long double d = (n * log10(1.6180339887498948)) - 
                    ((log10(5)) / 2); 
  
    return ceil(d); 
} 
  
// Driver program to test the above function 
int main() 
{ 
    long long i; 
    for (i = 1; i <= 10; i++) 
    cout << "Number of Digits in F("
         << i <<") - "
         << numberOfDigits(i) << "n"; 
  
    return 0; 
} 

Java

// Java program  to find number of digits in nth 
// Fibonacci number 
  
class GFG  
{ 
    // This function returns the number of digits 
    // in nth Fibonacci number after ceiling it 
    // Formula used (n * log(phi) - (log 5) / 2) 
    static double numberOfDigits(double n) 
    { 
        if (n == 1) 
            return 1; 
      
        // using phi = 1.6180339887498948 
        double d = (n * Math.log10(1.6180339887498948)) - 
                   ((Math.log10(5)) / 2); 
      
        return Math.ceil(d); 
    } 
  
    // Driver code 
    public static void main (String[] args) 
    { 
        double i; 
        for (i = 1; i <= 10; i++) 
        System.out.println("Number of Digits in F("+i+") - " 
                           +numberOfDigits(i)); 
    } 
} 
  
// This code is contributed by Anant Agarwal. 

Python3

# Python program to find  
# number of digits in nth  
# Fibonacci number 
import math 
  
# storing value of  
# golden ratio aka phi 
phi = (1 + 5**.5) / 2
  
# function to find number  
# of digits in F(n) This  
# function returns the number  
# of digitsin nth Fibonacci  
# number after ceiling it 
# Formula used (n * log(phi) -  
# (log 5) / 2) 
def numberOfDig (n) : 
    if n == 1 : 
        return 1
    return math.ceil((n * math.log10(phi) - 
                      .5 * math.log10(5))) 
  
// Driver Code 
for i in range(1, 11) : 
    print("Number of Digits in F(" + 
                   str(i) + ") - " + 
                str(numberOfDig(i))) 
  
# This code is contributed by SujanDutta 

C#

// C# program to find number of  
// digits in nth Fibonacci number 
using System; 
  
class GFG { 
      
    // This function returns the number of digits 
    // in nth Fibonacci number after ceiling it 
    // Formula used (n * log(phi) - (log 5) / 2) 
    static double numberOfDigits(double n) 
    { 
        if (n == 1) 
            return 1; 
      
        // using phi = 1.6180339887498948 
        double d = (n * Math.Log10(1.6180339887498948)) - 
                   ((Math.Log10(5)) / 2); 
      
        return Math.Ceiling(d); 
    } 
  
    // Driver code 
    public static void Main () 
    { 
        double i; 
        for (i = 1; i <= 10; i++) 
        Console.WriteLine("Number of Digits in F("+ i +") - "
                           + numberOfDigits(i)); 
    } 
} 
  
// This code is contributed by Nitin Mittal. 

PHP

<?php 
// PHP program to find number of  
// digits in nth Fibonacci number  
  
// This function returns the 
// number of digits in nth 
// Fibonacci number after  
// ceiling it Formula used  
// (n * log(phi) - (log 5) / 2) 
function numberOfDigits($n) 
{ 
    if ($n == 1) 
        return 1; 
  
    // using phi = 1.6180339887498948 
    $d = ($n * log10(1.6180339887498948)) - 
                          ((log10(5)) / 2); 
  
    return ceil($d); 
} 
  
    // Driver Code 
    $i; 
    for ($i = 1; $i <= 10; $i++) 
    echo "Number of Digits in F($i) - "
         , numberOfDigits($i), "
"; 
  
// This code is contributed by nitin mittal 
?> 

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Finding number of digits in n’th Fibonacci number

C++

Java

Python3

C#

PHP

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books