An efficient way to check if the nth Fibonacci number is a multiple of 10?

Here we will see an efficient way to check if the nth Fibonacci term is a multiple of 10. Suppose the Fibonacci terms are {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987}. So here the 15th Fibonacci number (counting from 0) is divisible by 10. For 16 it will return true.

One of the simplest ways is to generate Fibonacci numbers up to a given term and check if it is divisible by 10? But this solution is not good because it doesn't work for larger items.

Another good method is as follows-

Fibonacci terms- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 , 233, 377, 610, 987

These numbers (marked in bold letters) are divisible by 2. They are separated by 3 Fibonacci terms. Likewise, please check -

Fibonacci terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

Every fifth term is divisible by 5. Now the LCM of 3 and 5 is 15. So we can say that every 15^th Fibonacci term is divisible by 10.

Let's look at the algorithm to understand this idea.

Algorithm

fiboDivTen(term)

Begin
   if term is divisible by 15, then
      return true
   end if
   return false
End

Example

’s Chinese translation is:

Example

#include<iostream>
using namespace std;
bool fiboDivTen(int term) {
   if(term % 15 == 0){
      return true;
   }
   return false;
}
int main() {
   int term = 45;
   if (fiboDivTen(term))
      cout << "Divisible";
   else
      cout << "Not Divisible";
}

Output

Divisible

The above is the detailed content of An efficient way to check if the nth Fibonacci number is a multiple of 10?. For more information, please follow other related articles on the PHP Chinese website!