patterncsharpModerate
Sum even fibonacci numbers up to a limit
Viewed 0 times
fibonaccilimitnumberssumeven
Problem
After I have tackled the first problem I come to Project Euler Problem 2 which states
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.
If we take into account that
we only need to take every third term.
But before we can get there we need to get all the fibonacci numbers like so
which will generate infinite terms of the fibonacci numbers. We will then restrict this by using the
Getting only the even terms up to a specific limit can be achieved by
which is called by the
As usual any improvements in style, performance, naming or memory usage are welcome.
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.
If we take into account that
- adding 2 odd numbers will result in an even number
- adding an odd to an even number will result in an odd number
we only need to take every third term.
But before we can get there we need to get all the fibonacci numbers like so
private static IEnumerable GetFibonacciNumbers()
{
var first = 0;
var second = 1;
while (true)
{
var nextFibonacciNumber = first + second;
yield return nextFibonacciNumber;
first = second;
second = nextFibonacciNumber;
}
}which will generate infinite terms of the fibonacci numbers. We will then restrict this by using the
TakeWhile() extension method.Getting only the even terms up to a specific limit can be achieved by
private static IEnumerable GetEvenFibonacciNumbersTill(int upperLimit)
{
var counter = 0;
foreach (var currentTerm in GetFibonacciNumbers().TakeWhile(i => i < upperLimit))
{
counter++;
if (counter == 3) // every third term is even
{
yield return currentTerm;
counter = 0;
}
}
}which is called by the
int Solve() method like soprivate static readonly int fourMillions = 4000000;
public static int Solve()
{
return GetEvenFibonacciNumbersTill(fourMillions).Sum();
}As usual any improvements in style, performance, naming or memory usage are welcome.
Solution
If you dig a little deeper in the math, it is very straightforward to realize that every third Fibonacci number can be computed with the formula:
\$F_{n+6} = 4 F_{n+3} + F_{n}\$
You can reuse your function if you work the recursion backwards a couple of steps, and do something like:
This will not only make your code ~3x faster, but will render your other functions trivial to write.
\$F_{n+6} = 4 F_{n+3} + F_{n}\$
You can reuse your function if you work the recursion backwards a couple of steps, and do something like:
private static IEnumerable GetEvenFibonacciNumbers()
{
var first = 2;
var second = 0;
while (true)
{
var nextFibonacciNumber = first + 4*second;
yield return nextFibonacciNumber;
first = second;
second = nextFibonacciNumber;
}
}This will not only make your code ~3x faster, but will render your other functions trivial to write.
Code Snippets
private static IEnumerable<int> GetEvenFibonacciNumbers()
{
var first = 2;
var second = 0;
while (true)
{
var nextFibonacciNumber = first + 4*second;
yield return nextFibonacciNumber;
first = second;
second = nextFibonacciNumber;
}
}Context
StackExchange Code Review Q#115581, answer score: 14
Revisions (0)
No revisions yet.