14
\$\begingroup\$

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

  • 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<int> 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<int> 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 so

private 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.

asked Jan 1, 2016 at 17:01
\$\endgroup\$

4 Answers 4

13
\$\begingroup\$

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:

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;
 }
} 

This will not only make your code ~3x faster, but will render your other functions trivial to write.

answered Jan 1, 2016 at 23:14
\$\endgroup\$
12
\$\begingroup\$

I think using more LINQ will benefit both readability and conciseness.

The Where method has an overload where the predicate function gets fed the index too, the type is:

public static IEnumerable<TSource> Where<TSource>( 
 this IEnumerable<TSource> source, 
 Func<TSource, int, bool> predicate 
)

So the code can become just:

public static int Solve()
{
 return FibonacciNumbers()
 .TakeWhile(i => i < upperLimit)
 .Where( (_, i) => i % 3 == 0)
 .Sum()
}

I also removed Get from the name of the function generating fibonacci numbers, as get has very precise meaning in OOP and using it when you do not mean that is confusing.

answered Jan 1, 2016 at 18:32
\$\endgroup\$
4
\$\begingroup\$

If it's performance you're after, enumerating all of the numbers in the sum is not the way to go.

Binet's formula is $$F(n) = \frac{\varphi^n-(-\varphi)^{-n}}{\sqrt5}$$ It's easy to show that the even Fibonacci numbers are \$F(3m)\$ for integer \$m\$.

So the goal is $$\sum_{m=0}^{M} F(3m) = \sum_{m=0}^{M} \frac{\varphi^{3m}-(-\varphi)^{-3m}}{\sqrt5}$$ and by splitting the sums, substituting \$\theta = \varphi^3\$, and using the standard closed form for a geometric sum we get $$= \frac{1}{\sqrt 5}\sum_{m=0}^{M} \theta^m- \frac{1}{\sqrt 5}\sum_{m=0}^{M} (-\theta^{-1})^m = \frac{1}{\sqrt 5} \frac{\theta^{M+1} - 1}{\theta - 1} + \frac{1}{\sqrt 5} \frac{(-\theta^{-1})^{M+1} - 1}{\theta^{-1} + 1} $$ which we can rearrange to $$ = \frac{1}{\sqrt 5} \frac{(\theta^{M+1} - 1)(\theta^{-1} + 1) + ((-\theta^{-1})^{M+1} - 1)(\theta - 1)}{(\theta - 1)(\theta^{-1} + 1)} \\ = \frac{1}{\sqrt 5} \frac{\theta^{M+1} -(-\theta)^{-(M+1)} + \theta^{M} - (-\theta)^{-M} - \theta^{-1} - \theta}{(\theta - \theta^{-1})} \\ = \frac{1}{4} \left[ \frac{\theta^{M+1} -(-\theta)^{-(M+1)}}{\sqrt 5} + \frac{\theta^{M} - (-\theta)^{-M}}{\sqrt 5} - \frac{\theta -(-\theta)^{-1}}{\sqrt 5} \right] \\ = \frac{F(3M+3) + F(3M) - F(3)}{4} $$

Then the calculation can be done in logarithmic time using either floating point or matrix exponentiation.

answered Dec 12, 2019 at 16:03
\$\endgroup\$
3
  • \$\begingroup\$ Thanks Peter, I need to check where my rusty math went ;-) \$\endgroup\$ Commented Dec 13, 2019 at 5:10
  • \$\begingroup\$ Sorry somehow I have overseen the language of the wiki. \$\endgroup\$ Commented Dec 13, 2019 at 9:39
  • \$\begingroup\$ @Heslacher, overlooked. No worries, changing a link destination is an easy edit. \$\endgroup\$ Commented Dec 13, 2019 at 9:40
2
\$\begingroup\$

I just wanted to offer an alternative answer to your implementation that I discovered after trying to come up with a cool way to do Euler's #2.

The algorithm uses an equation I discovered: Fib(x+3) = 4*Fib(x) + Fib(x-3) (this works for x> 3, otherwise assume Fib(x-3) is 0).

Due to the nature of the fibonacci sequence we know that every 3rd fibonacci number is even. The equation above only uses every 3rd fibonacci, which means we can calculate all even fibonacci numbers without calculating the odds one at all.

Here's the code:

int fib = 2, sum = 0, holder = 0;
while (fib < 4000000)
{
 sum += fib;
 int swapper = fib;
 fib = 4 * fib + holder;
 holder = swapper;
}
Heslacher
50.9k5 gold badges83 silver badges177 bronze badges
answered Jan 7, 2016 at 21:04
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.