odd + odd = even

odd + even = odd

even + odd = odd

F0 = 0, F1 = 1, F2 = 1, F3 = 2, ...

So every third number is even. You only need to count the number of numbers divisible by three in the interval.

More generally, If Fi is the smallest fibonacci number such that a | Fi, then a | Fj iff j = 0 (mod i). This holds since gcd(Fa, Fb) = F(gcd(a, b))

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

Instead, it is equivalent to the sum of all values in the fibonacci sequence between indicies n and m, and the fibonacci numbers are taken modulo 2. We can also form them (summing up) modulo 2. This can be used to count the number of odd values (for even, just taken m - n + 1 - count_odd).

Instead of counting odds in the range, we can also count the odds in ranges [1, m] and [1, n — 1] and subtract the answers.

Let's form the first values of the fibonacci sequence modulo 2:

0 1 1 0 1 1 0 1 1 0 .... Notice that there's a cycle of length 3, of the form 0 1 1. We can use this property:

The number of odds in the range [1, x] (where 1 and x are indicies in the fibonacci sequence) is equal to:

Edit: you can also count instead the number of even values (which should be easier), as said in the comment above me.

Can you share the question link!!