The sum of the even fibonacci numbers

Question

This is the Euler project problem. If you do not want to see that the candidate’s decisions do not look here.

Hello everybody! I am developing an application that will find the sum of all even members of a fibonacci sequence. The last member of this sequence is 4,000,000. There is something wrong with my code, but I cannot find the problem, because it makes sense to me. Can you help me?

using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { long[] arr = new long [1000000] ; long i= 2; arr[i-2]=1; arr[i-1]=2; long n= arr[i]; long s=0; for (i=2 ; n <= 4000000; i++) { arr[i] = arr[(i - 1)] + arr[(i - 2)]; } for (long f = 0; f <= arr.Length - 1; f++) { if (arr[f] % 2 == 0) s += arr[f]; } Console.Write(s); Console.Read(); } } } 

Answer 1

Change the first for loop to this:

 for (i = 2; arr[i - 1] < 4000000; i++) 

Answer 2

Use this: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

Third identity This identity has slightly different forms for Fj, depending on whether j is odd or even. The sum of the first n - 1 Fibonacci numbers, Fj, such that j is odd, is the number (2n) th Fibonacci.

The sum of the first n Fibonacci numbers, Fj, such that j is even, is the number of the (2n + 1) th Fibonacci number minus 1.

[16]

The only problem is the potential loss of accuracy when summing phi to (2n + 1) th power.

Answer 3

In this section:

  long n= arr[i]; long s=0; for (i=2 ; n <= 4000000; i++) { arr[i] = arr[(i - 1)] + arr[(i - 2)]; } 

You assigned n only once; n never updated, so your loop will never end.

n not tied to i ; n set to arr[2] because i was 2 at this point. So i will be 3 from the first iteration of the loop forever.

To fix this, one way would be to get rid of n as a whole and make your loop condition

 for (i = 2; arr[i] <= 4000000; i++) 

Answer 4

try this (and use it for your big integer requirements: http://intx.codeplex.com/Wikipage ):

 using System; using System.Collections; using System.Linq; using System.Collections.Generic; using Oyster.Math; namespace Application { public class Test { public static void Main() { IntX even = 0; Console.WriteLine("Sum of even fibonacci {0}\n", Fibonacci(20).Where(x => x % 2 == 0).Sum()); Console.WriteLine("Sum of odd fibonacci {0}", Fibonacci(20).Where(x => x % 2 == 1).Sum()); Console.Write("\nFibonacci samples"); foreach (IntX i in Fibonacci(20)) Console.Write(" {0}", i); Console.ReadLine(); } public static IEnumerable<IntX> Fibonacci(int range) { int i = 0; IntX very = 0; yield return very; ++i; IntX old = 1; yield return old; ++i; IntX fib = 0; while (i < range) { fib = very + old; yield return fib; ++i; very = old; old = fib; } } } public static class Helper { public static IntX Sum(this IEnumerable<IntX> v) { int s = 0; foreach (int i in v) s += i; return s; } } } 

Output Example:

 Sum of even fibonacci 3382 Sum of odd fibonacci 7563 Fibonacci samples 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

Answer 5

I admit that I will do it in a completely different way. I would probably use a pair sequence of Lucas and Fibonacci numbers, as well as simple formulas

F (n + a) = (F (a) * L (n) + L (a) * F (n)) / 2

L (n + a) = (5 * F (a) * F (n) + L (a) * L (n)) / 2

Please note that only the third Fibonacci number is even. Since F (3) = 2 and L (3) = 4, we obtain

F (n + 3) = L (n) + 2 * F (n)

L (n + 3) = 5 * F (n) + 2 * L (n)

Now just summarize the terms.

(edit: there is an even simpler solution to this question, which relies on some mathematical complexity to obtain either some knowledge of the Fibonacci sequence and identities for this sequence or, possibly, searching the encyclopedia of integer sequences., moreover, this hint seems unacceptable for the PE problem , so I will leave this decision in the margins of this note. Thus, the sum of the first k even Fibonacci numbers ...)