CODEWITHSUNDEEP
javascript
ophunt
ophunt

Reputation: 100

Having trouble with the Fibonacci Sequence

So I recently discovered this site (https://projecteuler.net). The second problem asks you to find the sum of all even Fibonacci numbers less than four million. I tried to use my limited JavaScript to solve this for me, but it doesn't seem to be working at all. Here is the jsfiddle: http://jsfiddle.net/ophunt/pnf24j7q/3/

Here is the javascript contained therein:

//variables here
var sum = 0;
var fibA = 1;
var fibB = 1;
var store = 0;

//main loop
while (fibA < 4000000) {
    store = fibA;
    fibA += fibB;
    fibB = store;
    if (fibA % 2 === 0) {
        sum += fibA;
    }
}

Document.getElementById("result").innerHTML = sum;

Upvotes: 1

Views: 279

Answers (1)

Mark
Mark

Reputation: 92440

So a few things can help you out here:

  1. The sum up to fibonacci(n) = fibonacci(n+2) - 1 This is nice since you don't have to manually do the sums since you are already doing the sums when you create the sequence

  2. Even fibonacci numbers are every third fibonacci number. This ends up meaning that the sum of the evens is equal to the sum of all divided by two.

For example:

fibs:     1, 1, 2, 3, 5,  8,  13, 21, 34, 55, 89
sums:     1, 2, 4, 7, 12, 20, 33, 54, 88
even_sum: 0, 0, 2, 2, 2,  10, 10, 10, 44
  1. Also give a number you can find the which fiboncacci is closest with exceeding it based on some (semi)simple math. (You can also calculate the fibonacci numbers themselves this way, but I'll leave the original function because recursive functions are cool.

The javascript implimentation looks like this:

var findFibNum = function(num) {
    var est = Math.log(num * Math.sqrt(5)) /(Math.log((Math.sqrt(5)+1)/2))
    return Math.floor(est)  
}

Knowing these three things you can make a pretty quick solution:

var top = 4000000;

/* function finds nth fibonacci number */
var fib = function(n){
    if (n <=1) return n;
    return fib(n-1) + fib(n-2);
}

/* given a number this finds closest n below it i.e. for 34 it give 9
   because 34 is the nineth fibonacci number
*/
var findFibNum = function(num) {
    var est = Math.log(num * Math.sqrt(5)) /(Math.log((Math.sqrt(5)+1)/2))
    return Math.floor(est)  
}


var n = findFibNum(top) /* fib(n) is the largest fibonacci below top */

/* the sum of fibonacci number n is fib(n)+2 -1 -- this beats looping and adding*/
var fibsum = fib(n+2) -1

/* it s a nice feature of the sequence that the sum of evens is equal to the sum off all dived by 2 */
var evensum = fibsum/2

Fiddle gives 4613732

Upvotes: 1

Related Questions