In the Fibonacci sequence, F 0 = 1 , F 1 = 1 , and for all N > 1 , F N = F N − 1 + F N − 2 .
How many of the first 2014 Fibonacci terms end in 0?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
note the formula G C D ( F n , F x ) = F G C D ( n . x ) ) for F n = ⎩ ⎪ ⎨ ⎪ ⎧ = 0 f o r n = 0 = 1 f o r n = 1 = F n − 1 + F n − 2 f o r n ≥ 2 now, note that F 1 5 is the first Fibonacci >0 dividable by 10. use the GCD formula, and lets see for a few G C D ( F 1 5 , F 3 0 ) = F G C D ( 1 5 , 3 0 ) = F 1 5 = 0 ( m o d 1 0 ) G C D ( F 3 0 , F 4 5 ) = F G C D ( 3 0 , 4 5 ) = F 1 5 = 0 ( m o d 1 0 ) G C D ( F 4 5 , F 6 0 ) = F G C D ( 4 5 , 6 0 ) = F 1 5 = 0 ( m o d 1 0 ) since GCD of these are 0 mod 10 these end with zero. but any n not divisible by 15 wont end with 0. there are 1 3 4 multiples of 15 from 1 to 2015
Amazing ..learnt something new. It was great fun looking at list of Prime factorized forms of Fibonacci sequence members ...after knowing this GCD property!
Note that a Fib number end with a 0 every 15 numbers, so just divide 2014 by 15 and take the greatest integer function of the quotient, which is 134.
After some computation, it is easy to see that F 1 4 ends with 0. Now, we want to prove by induction that all Fibonacci numbers in the form F 1 5 n − 1 end in 0. Since we already stated the base case, it suffices to show that our claim holds for all of these numbers. Let n denote the unit's digit of F 1 5 n − 2 . Thus, we can express the units digit (in m o d 1 0 ) as n , 0 , n , 2 n , 3 n , 5 n . . . . . . The coefficients of n are equivalent to the first 15 Fibonacci numbers (treating zero as F 0 )! Thus, our claim is valid, and for every 15 consecutive terms, there is one term whose last digit is 0. Thus, our answer is ⌊ 1 5 2 0 1 4 ⌋ = 1 3 4
Whoops, note in the above solution, I made a mistake on lines 5 and 6. First, you do not have to treat F 0 as 0. Secondly, the terms should be n , 0 , n , n , 2 n , 3 n , 5 n . . . instead of the terms listed in the solution.
simple elegant code in C : #include <stdio.h>
int main(){
int i,s=0,f0=1,f1=1;
for (i=2;i<2014;i++){
f1=(f0+f1)%10;
f0=(f1-f0)%10;
if (!f1)
s++;
}
printf("%d",s);
return 0;
}
P.S. : I used f1 (mod 10) and f2 (mod 10) because we only need the unit number
We use another sequence with numbers from 0 to 9 that satisfy fn = xn (mod 10). It can be proven that this sequence repeats, and through trial shows that it repeats itself every 60 numbers, which include 4 0s the first 34 numbers include 2 0s So 134 is the answer
Problem Loading...
Note Loading...
Set Loading...
Running this code gives you the Answer: 134