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 15th Fibonacci term is divisible by 10.
Let's look at the algorithm to understand this idea.Begin if term is divisible by 15, then return true end if return false End
#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"; }
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!