FreeCodeCamp: Sum All Odd Fibonacci Numbers

Here is one of the Algorithm challenges from FreeCodeCamp: Intermediate Algorithm Scripting: Sum All Odd Fibonacci Numbers:

Given a positive integer num, return the sum of all odd Fibonacci numbers that are less than or equal to num.

The first two numbers in the Fibonacci sequence are 1 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first six numbers of the Fibonacci sequence are 1, 1, 2, 3, 5 and 8.

For example, sumFibs(10) should return 10 because all odd Fibonacci numbers less than or equal to 10 are 1, 1, 3, and 5.

I wrote a silly solution using JavaScript generators:

function* fibonacci() {
  let [a, b] = [0, 1];
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

function* filter(iterable, filterFunc) {
  for (const x of iterable) {
    if (filterFunc(x)) {
      yield x;
    }
  }
}

function* takeWhile(iterable, predicate) {
  for (const x of iterable) {
    if (!predicate(x)) return;
    yield x;
  }
}

const isOdd = x => x % 2 !== 0;

const reduceSum = arr => arr.reduce((prev, curr) => prev + curr);

const sumOddFibs = num => {
  return reduceSum([...takeWhile(filter(fibonacci(), isOdd), x => x <= num)]);
};

It’s hard to understand so I wouldn’t write it in production code. But it was a useful thinking exercise.

The function sumOddFibs uses the fibonacci generator to create an infinite stream of Fibonacci numbers. The filter generator is responsible for only generating odd numbers with the helper function isOdd.
This is all in “abstract land” and doesn’t result in a finite array of numbers.

Now, we have to go down to the “real world”. We use takeWhile and the spread syntax to create an array of all the (abstract) odd Fibonacci numbers that are smaller or equal to the input number.

And at the end, just reduce over this array to get the sum of all those numbers.

Similar Clojure code looks like this:

(def fibo-seq
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

(defn fibo-cnt [n]
  (->> fibo-seq
      (take-while (partial > n))
      (filter odd?)
      (reduce +)))

fibo-seq creates the infinite sequence of Fibonacci numbers.
In our main function fibo-count we use the thread-first macro to pipe this sequence into a number of transformations. We only take a subset of numbers that are smaller than the input number (with take-while and partial), then we filter for odd numbers. Finally, we use reduce to sum up all numbers.

FreeCodeCamp: Sum All Odd Fibonacci Numbers

Further Reading