# Even Fibonacci numbers

Today, I found the Euler Project. Problem #2 is

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.

I have two solutions:

For[i = 1, i < 100, i++, If[Fibonacci[i] > 4000000, Break[]]];
Plus @@ Select[Fibonacci /@ Range[i - 1], Mod[#, 2] == 0 &]


4613732

Plus @@ Select[
Fibonacci /@ Select[Range@100, Fibonacci@# < 4000000 &],
Mod[#1, 2] == 0 &]


4613732

However, I feel my solutions are not good and efficient. So my question is: can you show me more concise and efficient methods?

Also, how cam I test whether a number is a Fibonacci number？

-
Since you already have the answer, you may access the problem 2 forum on the Euler project. Here you will find the most efficient algorithms from other users. The third post there demonstrates an algorithm that can be easily calculated without a program. –  trav1s Nov 19 '13 at 5:38

The other methods described work well, but I am partial to exact answers. So, here it is. First, note that the Fibbonacci sequence has a closed form

$$F_n = \frac{\Phi^n - (-\Phi)^{-n}}{\sqrt{5}}$$

where $\Phi$ is the GoldenRatio. Also, as observed elsewhere, we are looking only at every third term, which gives the sum

$$\sum^k_{n = 1} \frac{\Phi^{3n} - (-\Phi)^{-3n}}{\sqrt{5}}$$

which is just the sum of two geometric series. So, after a few steps, this simplifies to

$$\frac{1}{\sqrt{5}} \left[ \Phi^3\frac{1 - (\Phi^3)^{k}}{1-\Phi^3} + \Phi^{-3}\frac{1 - (-\Phi^{-3})^{k}}{1 + \Phi^{-3}} \right]$$

where $k$ is the index of the highest even Fibbonacci number. To find $k$, we can reverse the sequence,

n[F_] := Floor[Log[F Sqrt[5]]/Log[GoldenRatio] + 1/2]
n[4000000]
(* 33 *)


So, $k = 11$. In code,

Clear[evenSum];
evenSum[(k_Integer)?Positive] :=
Round @ N[
With[
{phi = GoldenRatio^3, psi = (-GoldenRatio)^(-3)},
(1/Sqrt[5])*(phi*((1 - phi^k)/(1 - phi)) - psi*((1 - psi^k)/(1 - psi)))
],
Max[\$MachinePrecision, 3 k] (* needed for accuracy *)
]

evenSum[11]
(* 4613732 *)


which is confirmed by

Total @ Fibonacci @ Range[3, 33, 3]
(* 4613732 *)


Edit: The above implementation of n suffers round off problems for large numbers, for example n[9000] gives 21, but Fibonacci[21] is 10946. But, wikipedia gives a better choice

Clear[n2];
n2[fn_Integer?Positive] :=
Floor@N@Log[GoldenRatio, (fn Sqrt[5] + Sqrt[5 fn^2 - 4])/2]

n2[10945]
(* 20 *)

-
Had to fix the formulas, I dropped quite a few minus signs in the original version. –  rcollyer Nov 18 '13 at 18:04
Related to your error, of course facebook.com/physic.department/posts/360869444018997 –  belisarius Nov 18 '13 at 18:25
@belisarius :)) ingenious. –  Stefan Nov 18 '13 at 18:27
@belisarius according to my adviser, his adviser was infamous for making multiple canceling errors. His results were correct, the derivation not usually. :) –  rcollyer Nov 18 '13 at 18:31
Could you explain how these functions n and evenSum should be used for big numbers? I tried to test your solution unsucessfully. While with mine approach I could simply find sums up to 10^10000. –  Artes Nov 18 '13 at 18:36

Straight iteration over the even valued Fibonacci numbers is fast.

fibSum[max_] := Module[
{tot, n, j},
tot = 0;
n = 0;
j = 3;
While[n = Fibonacci[j]; n <= max, j += 3; tot += n];
tot]


Or one can use matrix products. This seems to be about the same speed. It has the advantage of not requiring a built in Fibonacci function.

fibSum2[max_] := Module[
{tot, n, fp, mat, mat3},
mat = {{0, 1}, {1, 1}};
tot = 0;
n = 0;
fp = mat.mat;
mat3 = mat.mat.mat;
While[n = fp[[2, 2]]; n <= max, fp = fp.mat3; tot += n];
tot]


These handle 10^10000 in slightly under a second on my desktop running Mathematica 9.0.1.

Here is a test for whether an integer is a Fibonacci number (a Fib detector?)

fibQ[n_] :=
With[{k =
Round[Log[GoldenRatio, N[n, 20 + Length[IntegerDigits[n]]]] +
Log[GoldenRatio, Sqrt[5]]]},
n == Fibonacci[k]]

-
You need to correct 10^10000. –  Ramchandra Apte Nov 19 '13 at 10:35
[Correct it how? Will a good spanking suffice?] –  Daniel Lichtblau Nov 19 '13 at 15:22
My mistake; I read it as 10^10000 numbers in slightly under a second. –  Ramchandra Apte Nov 19 '13 at 16:06
Sum[Fibonacci[n],
{n, 3, InverseFunction[Fibonacci][4000000], 3}]

(* 4613732 *)

-
That's tyte, + goes w/o saying. –  alancalvitti Oct 30 '14 at 18:18

Your solution looks fine. You can take advantage of the fact that every third Fibonacci number is even, which makes it a little faster. Fibonaccis are cheap to compute and they quickly exceed 4 million. Here's a comparison:

Select[Fibonacci[3 Range@33], # <= 4*^6 &] // Total // AbsoluteTiming


{0.000214, 4613732}

Select[Fibonacci@Range@100, # <= 4*^6 && EvenQ@# &] // Total // AbsoluteTiming


{0.000566, 4613732}

Plus @@ Select[Fibonacci /@ Select[Range@100, Fibonacci@# < 4000000 &], Mod[#1, 2] == 0 &] // AbsoluteTiming


{0.000717, 4613732}

AbsoluteTiming[ For[i = 1, i < 100, i++, If[Fibonacci[i] > 4000000, Break[]]]; Plus @@ Select[Fibonacci /@ Range[i - 1], Mod[#, 2] == 0 &]]


{0.000526, 4613732}

-

Here I'd like to show my solution.

Since A014445 we know that the generating function of even fibonacci numbers is Fibonacci[3 n], we can write something like this:

Plus @@ Select[Table[Fibonacci[3 n], {n, 0, 30}], # < 4000000 &] // AbsoluteTiming

=> {0., 4613732}


An imperative style solution could look like this:

res = 0; n = 1; While[res < 4000000, res += Fibonacci[3 n]; n++]


Result will be in res and timings are negligible, zero.

Edit: To bring that into a cogent form. Here the full definition of SumEvenFibonacci:

ClearAll[SumEvenFibonacci];
SumEvenFibonacci::usage =
"SumEvenFibonacci[n] calculates the sum of even Fibonacci numbers \
up to the upper-bound n.";
SumEvenFibonacci[n_Integer] /; n >= 0 := Module[{res = 0, i = 1},
While[res < n, res += Fibonacci[3 i]; i++];
res
]

-

The Fibonacci function, is Listable and fast increasing. We can observe a simple pattern, every third element is even (see e.g. Fibonacci[Range[12]]), moreover the first number exceeding 4000000 is: NestWhile[(# + 1) &, 1, Fibonacci[#] <= 4 10^6 &], thus we have:

Total[ Fibonacci[ Range[3, 33, 3]]]

4613732


and most likely this is the best approach:

sum[n_] := Total[ Fibonacci[ Range[3, NestWhile[(# + 1) &, 1, Fibonacci[#] <= n &] - 1, 3]]]


e.g.

sum[10^600]; // AbsoluteTiming

{0.096000, Null}


Concerning testing if given numbers are Fibonacci ones there is a simple test based on checking if consecutive elements generate Pythagorean triples (see e.g. this answer)

And @@ (#1^2 + #2^2 == #3^2 & @@@
Array[{  Fibonacci[#] Fibonacci[# + 3],
2 Fibonacci[# + 1] Fibonacci[# + 2],
Fibonacci[# + 1]^2 + Fibonacci[# + 2]^2} &, 1000])

True

-
You already got my +1, but, yeah, it looks a little cretinous. –  rcollyer Nov 18 '13 at 21:14
@rcollyer I like your approach, but I still cannot use it successfully. I guess Daniel Lichtblau's solution is the most efficient for big numbers, however I can see that another reliable (mine) solution is the least appreciated. –  Artes Nov 18 '13 at 21:20
A little poking around indicates that n gives the nearest Fibbonacci number, not the one immediately below it, e.g. n[9000] returns 21, not 20. Likely a similar rounding issue is occurring in evenSum, but it tracks Daniel's exactly for a long time. So, I'm not sure of the specific issue. –  rcollyer Nov 18 '13 at 21:30

## protected by Verbeia♦Nov 17 '14 at 1:30

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.