A program to find out the number of odd and even Fibonacci numbers between given range I built a program in C that can tell how many odd and even Fibonacci numbers there are between a given range. 


  Input Specification 
  
  First line of the input contains T, representing the number of test cases (1 ≤ T ≤ 50). Each test case contains two integers N and M (1 ≤ N ≤ M ≤ 1018) and (|N-M| ≤ 105), where N is the Nth Fibonacci number and M is the Mth Fibonacci number of the sequence. 
  
  Output Specification
  
  Case T:
  Odd = total number of odd Fibonacchi numbers between N and M
  Even = total number of even Fibonacchi numbers between N and M   


The full code

#include &lt;stdio.h&gt;
#include &lt;math.h&gt;

int main()
{
    int T, i, j, k;
    scanf("%d", &amp;T);

    for (i=0; i&lt;T; i++)
    {
        int N, M, val;
        scanf("%d%d", &amp;N,&amp;M);
        val = abs(N-M)+1;

        int n,m;
        if (M&gt;N) { n=N; m=M; }
        if (N&gt;M) { n=M; m=N; }

        int b_tri, e_tri, even=0, odd=0;
        if (n%3==1) { b_tri=3; even++; odd+=2; } 
        if (n%3==2) { b_tri=2; odd+=2; }
        if (n%3==0) { b_tri=1; odd++;  }

        if (m%3==1) { e_tri=1; even++; } 
        if (m%3==2) { e_tri=2; odd++;  even++; }
        if (m%3==0) { e_tri=3; odd+=2; even++; }

        val-=(e_tri+b_tri);
        val/=3;

        for (j=0; j&lt;val; j++)
        {
            even++;
            odd+=2;
        }

        printf("Case %d:\nOdd = %d\nEven = %d\n", i+1, odd, even);
    }

    return 0;
}


Logic


1st Fibonacci number is 0 (even).
2nd Fibonacci number is 1 (odd).
3rd Fibonacci number is 1 (even + odd = odd). 
4th Fibonacci number is 2 (odd  + odd = even).
5th Fibonacci number is 3 (odd + even = odd).
6th Fibonacci number is 5 (even + odd = odd).
7th Fibonacci number is 8 (even).
8th Fibonacci number is 13 (odd).
9th Fibonacci number is 21 (odd).




I'd like advice on:


Using mathematical formulas instead of loops to calculate this
Making the code more efficient
I'm going to assume you tested it for several inputs and got the right values. Your logic seems right so if a couple test cases work, it probably works. But I didn't look carefully for any off-by-one like errors.

There is one logic issue that I see:

You don't set n and  m if N = M. Double check your two if statements in the beginning of the loop; you only check for strict inequality on both sides. One of them should change to a &gt;= or &lt;=, or better yet just use if-else instead of two ifs.

As for optimization...

In terms of an average computer, your program is good enough for any N and M because you specify N,M &lt; 1018. Even if you don't, for-loops by themselves are pretty cheap.

However, there are still optimizations/cleanups. 

The biggest one is your last for loop:

for (j=0; j&lt;val; j++)
{
    even++;
    odd+=2;
}


This can just be: 

even+=val;
odd+=2*val


Your two if chains can turn into if, else if, else instead of three ifs (same thing for your first if pair, which should just be if else)

if (...) { }
else if (...) { }
else (...) { }


although the compiler will most likely optimize that for you.

I think that's the best you can do for your current algorithm.

However, it seems odd to me that you are checking for all mod cases for n and m; I think your idea is that you know the pattern for the large chunks in between N and M but you want to trim off the edge cases. Now, you won't need to trim down the case when n%3==1 or m%3==0, because you can just treat that as the even++, odd+=2 chunk.

n=m case

In programming you can always cop out :)

Here is how I would address the n=m case even though it's not too beautiful:

if (N == M)
{
  printf("Odd: 0, Even: 0"); //format this to match your output
  break;  // break ends the current for loop iteration in this context
}
else if (N &gt; M)
{
  n = M; m = N;
}
else
{
  n = N; m = M;
}