Project Euler - Problem 2: Even Fibonacci Numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
$$1,\; 2,\; 3,\; 5,\; 8,\; 13,\; 21,\; 34,\; 55,\; 89,\; ...$$
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

---

Explanation:

The simplest way to solve this is to loop over the Fibonacci generation and add all numbers that are divisible by 2 in the Fibonacci sequence <= 4,000,000.

Solution:

public static void Main()
{
    int left = 1;
    int right = 2;
    int sum = 2;
    while(right < 4000000)
    {
      int tmp = right;
      right = left + right;
      if(right % 2 == 0)
      {
        sum += right;
      }
      left = tmp;
    }
    Console.WriteLine(sum);
}

This simple solution can be found here.
The solution provided at the URL also provides the amount of ticks taken to produce that result. If you run it multiple times, you should see the amount of time varies slightly but still is not optimal. We could try improving on this value by being smarter about the number of comparisons we make or coming up with a better way to calculate the sum sequentially. Our goal reduce the scope of the problem so the computer is spending less time calculating the various values for us.

A Slightly Optimized Solution

A simple optimization we can perform is to only add every third number, since we know that every third number will be an even one. We can prove this by knowing that only when two odd numbers are added will we get an even number (by some basic number theory). This occurs every third number except when we first start. You could provide a much better proof of this, but I am hoping that you see it.

public const int Limit = 4000000;

public static void Main()
{
    int left = 1;
    int right = 1;
    int temp = left + right;
    int sum = 0;
    while(temp < Program.Limit)
    {
      sum += temp;
      left = right + temp;
      right = temp + left;
      temp = left + right;
    }
    Console.WriteLine(sum);
}

The solution can be found here.
This solution also provides the amount of ticks taken to produce the result. As you can see this does not really save us much overhead.

Another Solution

Another solution is to figure out what the generating sequence for the even numbers in the Fibonacci sequence is. If we only write the even numbers we should get something like this: $$2,\; 8,\; 34,\; 144,\; ...$$ This is what we will use to solve for the function.
If we are given 2; 8 is 4 times that so it reasons that $$F(n)\; =\; 4\; *\; F(n-1)$$ However, this fails for F(3) since 8 * 4 = 32 not 34. But if we add the previous number (2) we get 34.
If we update our equation to be: $$F(n)\; =\; 4\; *\; F(n-1)\; +\; F(n-2)$$ we have a solution that seems to hold for these values. Try writing the code to test this out and see if the answer matches.

    public const int Limit = 4000000;

    static void Main()
    {
        long startTimeTicks = DateTime.Now.Ticks;
        int sum = RecursiveSolution(2, 8);
        Console.WriteLine(sum);
        long endTimeTicks = DateTime.Now.Ticks;
        Console.WriteLine("Took {0} ticks", endTimeTicks - startTimeTicks);
    }
    
    private static int RecursiveSolution(int n2, int n1)
    {
        int newN = 4 * n1 + n2;
        
        if(newN > Program.Limit)
        {
            return n2 + n1;
        }
        
        return n2 + RecursiveSolution(n1, newN);
    }

The solution can be found here.

Conclusion

Surprisingly the last method (at least for me) takes just as long if not longer to execute as the previous solutions. The lowest I got was 407180 ticks (but on average it was on par with the others). We could probably improve it slightly be not creating an integer every time we recurse, but I suspect the most time is spent pushing and popping items off the stack instead of updating the value of the integers like we were previously - which does us little good as we cannot improve that.
Have another solution I did not cover? Have additional insight into how to improve the solutions provided? Have questions? Let me know in the comments.