//https://projecteuler.net/problem=2

//Sum of even Fibonacci numbers whose value <= 4 million?

​

//For a discussion of performance.now(), used to determine 

//computation time, see

//https://stackoverflow.com/questions/313893/how-to-measure-time-taken-by-a-function-to-execute

​

//Currently, three solutions are provided in this program.

​

//On my machine, rerunning the program several times results in

//very different reported performance times, 

//and which solution is fastest varies from one run to the next.

//I have guesses about why this is but haven't looked into it.

​

//SOLUTION 1

let f1 = 1, f2 = 1, f3 = f1 + f2;

let sum = 0;

let t0, t1; //start and end times of computation

​

t0 = performance.now();

while (f3 <= 4000000) {

  if (f3 % 2 === 0) {

    sum += f3;    

  }

  f1 = f2;

  f2 = f3;

  f3 = f1 + f2;

}

t1 = performance.now();

​

console.log("Soln 1: " + sum);

console.log("Computation time for Soln 1: " + (t1-t0) + " ms" );

​

//SOLUTION 2

sum = 0;

let seq = [1, 1]; //Fibonacci numbers F(n-1), F(n)

let term = 0;

​

t0 = performance.now();

while(term <= 4000000) {

    if (term % 2 === 0) {

      sum += term;

    }

    seq.push(seq[seq.length - 1] + seq[seq.length - 2]);

    term = seq[seq.length -1];

}

t1 = performance.now();

​

console.log("Soln 2: " + sum);

console.log("Computation time for Soln 2: " + (t1-t0) + " ms" );

​

//SOLUTION 3

sum = 0;

seq = [1, 1];

term = 0; //term of F(0) + F(3) + F(6) + ... = 0 + 2 + 8 + ...

​

//thirdFib() extends seq by F(n+1), F(n+2), F(n+3); returns F(n+1)

function thirdFib(arr) {

  for (let i = 0; i < 3; i++) {  

    arr.push(arr[arr.length - 1] + arr[arr.length - 2]);

  }

  return arr[arr.length - 3];

}

​

t0 = performance.now();

while(term <= 4000000) {

    sum += term;

    term = thirdFib(seq);

}

t1 = performance.now();

​

console.log("Soln 3: " + sum);

console.log("Computation time for Soln 3: " + (t1-t0) + " ms" );

​

//Rough check:

//Since ratio of consecutive terms ~ golden ratio phi ~1.6,

//and we're adding every third term, our series is approximately

//geometric with common ratio ~ 1.6 ^ 3 ~ 4 (roughly). So,

//our answer is roughly 2 + 8 + 32 + ... = sum 2 * 4 ^ k from

//k = 0 to 10 (can determine upper bound = 10 in various ways).

//Using the closed formula for the sum of a geometric series,

//our approximating sum is [2 / (1 - 4)] * [1 - 4^11] = 

//2,796,202. If we use phi^3 instead of the rough approximation of //4 as our common ratio, our approximation is ~4,870,846.

​

//Exact, analytical solution: 

//Using Binet's formula (which is fun

//to derive), we could obtain an exact solution. Our sum is 

//exactly sum phi^(3(k+1)) - psi^(3(k+1)) / sqrt(5) from k = 0 to //10. (Establishing the upper bound without a computer might

//require some work.) This can be decomposed into geometric sums,

//yielding the answer 

//1/sqrt(5)*[(phi^3-phi^36)/(1-phi^3)-(psi^3-psi^36)/(1-psi^3)],

//which evaluates to 4,613,732.