DEV Community

Cover image for Project Euler Problem 2 Solved with Javascript
Jared
Jared

Posted on • Originally published at codeburst.io

Project Euler Problem 2 Solved with Javascript

Welcome to Round Two of Project Euler! This time we're heading into the land of state management and that guy you've probably heard about: Fibonacci! I'm excited, are you excited?

Video Version

If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!

Problem 2: Even Fibonacci Numbers

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

Problem Statement

By considering the terms in the Fibonacci sequence that do not exceed the nth term, find the sum of the even-valued terms.

Solution

Breakdown of the Problem

Fibonacci sequence

It's stated in the problem, however, let's discuss what a Fibonacci sequence is a little bit and why it's important.

The next number is found by adding up the two numbers before it.

When we do this, it creates an interesting spiral, which is found in myriad places in nature.

https://media3.giphy.com/media/5uqc0f9rn3igw/giphy.gif

We could probably talk all day about Fibonacci, but let's get back to code.

Steps

  1. Generate Fibonacci sequence
    1. Add our first term(1) + our second term (2)
    2. Add product of our previous numbers to second term
  2. Check to see if the value is even, if so, add it to a total sum.
  3. Repeat, infinitely...

Fibonacci Sequence

Naive Approach

    function fiboEvenSum(n) {
        // setup placeholders for our three values
      let fibNumSum = 0; // product of our two numbers
      let fibCurrent = 0; // current number
      let fibNext = 1; // next number

      for (let i = 1; i <= n; i++) {
        // find next number
        let fibTotal = fibCurrent + fibNext;

        // set first number to second number
        fibCurrent = fibNext;

        // set second number to total
        fibNext = fibTotal;
            // make sure the value is even
        if (fibTotal % 2 == 0) {
          fibNumSum += fibTotal;
        }
      }

      // You can do it!
      return fibNumSum;
    }

    fiboEvenSum(10); //44

Modulo

I talked about what modulo is in my first article, but I need to clarify a couple things. When you evaluate a modulo expression, it gives you the remainder of the division of the two numbers. In the case of 15 % 4 , that will give us a remainder of 3 because:

  • 4 goes into 15 3 times.
  • 15 - 3 * 4 (12) = 3

Therefore, 15 % 4 = 3 or 15 / 4 = 3 remainder 3

I don't know if that explains it well enough...but, if it still doesn't make sense. Check out the video in the resources section below!

Algorithmic Approach

I'm not going to sit here and try and explain someone else's code. However, I found a pretty awesome way of solving this problem via CodeFay.

GitHub logo CodeFay / ProjectEuler100

Project Euler 100 Challenge

ProjectEuler100

I'm returning to FreeCodeCamp in 2020 to attempt the Project Euler 100 Challenge.

Will it be really as hard as Dark Souls? Probably, but I'm up for the challenge!

Solved Problems:

  1. Multiples of 3 and 5 - Jan 14, 2020
  2. Even Fibonacci Numbers - Jan 17, 2020
  3. Largest prime factor - Jan 18, 2020
  4. Largest palindrome product - Jan 26, 2020
  5. Smallest multiple - Jan 26, 2020
  6. Sum square difference - Jan 26, 2020
  7. 10001st prime number - Jan 28, 2020
  8. Largest product in a series - Jan 28, 2020
  9. Special Pythagorean triplet - Jan 28, 2020
  10. Summation of Primes - Jan 28, 2020

It's an elegant approach, as well as a faster one. When I tested it against my naive approach, it was generally about 20% faster. I suggest checking it out if you want to see some cool code!

Final Thoughts

This problem is fairly straight-forward. What I like about this problem is it gets us thinking about the "state" of our app. We define our three values at the top of our function, then manipulate them within the for loop. This reduces what we have to do after we get all the fibonacci values.

As always, I'm sure there is room for improvement. If you have recommendations, let me know!

Resources

Fibonacci Sequence

https://www.youtube.com/watch?v=pNXwzIohx8c&feature=emb_title

Oldest comments (0)