Fibonacci Time

1
2
3
4
5
6
7

a, b = 1, 1
total = 0
for n in range(2014):
    if (a % 10) == 0:
        total += 1
    a, b = b, a+b  # the real formula for Fibonacci sequence
print total

Running this code gives you the Answer: 134

note the formula $GCD ( F_n,F_x)=F_{GCD(n.x))}$ for $F_n =\begin{cases} =0\quad for\quad n=0\\ =1\quad for\quad n=1\\ = F_{n-1}+F_{n-2}\quad for\quad n\geq 2 \end{cases}$ now, note that $\quad F_{15}\quad$ is the first Fibonacci >0 dividable by 10. use the GCD formula, and lets see for a few $\begin{array}{c}GCD(F_{15},F_{30})=F_{GCD (15,30)}=F_{15} = 0\pmod {10}\\ GCD(F_{30},F_{45})=F_{GCD (30,45)}=F_{15} = 0\pmod {10}\\ GCD(F_{45},F_{60})=F_{GCD (45,60)}=F_{15} = 0\pmod {10}\\ \end{array}$ 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 $\quad \boxed{134}\quad$ multiples of 15 from 1 to 2015

After some computation, it is easy to see that $F_{14}$ ends with 0. Now, we want to prove by induction that all Fibonacci numbers in the form $F_{15n-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_{15n-2}$ . Thus, we can express the units digit (in $\mod{10}$ ) as $n, 0, n, 2n, 3n, 5n.....$ . 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 $\lfloor{\frac{2014}{15}}\rfloor=134$

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